题解 | 二叉搜索树与双向链表

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
// 前驱节点：用来记录我们中序遍历时，刚刚走过的“上一个节点”。在链表里，它就是当前节点的“左邻居”。
    public TreeNode pre = null;
// 头节点：用来记录双向链表的第一个节点（也就是整棵树里最小的那个节点），最后我们要把它返回。
    public TreeNode head = null;
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        // 如果节点是空的（走到树的尽头了），直接回去。
        if (pRootOfTree == null) return null;

        //【左】先顺藤摸瓜，一路递归到最左下角的节点。把左子树全部处理完毕。
        Convert(pRootOfTree.left);

        // 【中】核心处理逻辑开始，这里就是处理当前节点（pRootOfTree）的地方：
        if (pre == null) {
            // 如果 pre 是空的，说明什么？说明我们此时正站在中序遍历的【第一个节点】上！
            // 也就是整棵树最左下角、值最小的那个节点。
            pre = pRootOfTree;
            // 它也是整个双向链表的头，把它用 head 锁死，以后永远不改它了。
            head = pRootOfTree;
        } else {
            // 如果 pre 不为空，说明当前节点之前已经有处理过的“左邻居”了，我们要开始双向缝合：
            // 缝合第一针：让“左邻居”的右指针，指向当前节点。
            pre.right = pRootOfTree;

            // 缝合第二针：让当前节点的左指针，指向“左邻居”。
            pRootOfTree.left = pre;

            // 我们要继续往后走，所以当前节点变成了新的“左邻居”，留给下一个节点去缝合。
            pre = pRootOfTree;
        }

        //【右】当前节点缝合完之后，按照中序遍历规则，继续去处理它的右子树。
        Convert(pRootOfTree.right);

        // 等所有递归跑完，整棵树都缝合完毕，我们把一开始锁死的最左边的头节点返回。
        return head;
    }
}