35.复杂链表的复制 #

class Solution {
    // 全局变量，存储头结点，上一个结点
    Node pre,head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        // 从根节点开始遍历
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    public void dfs(Node cur){
        // 基于中序遍历进行改造
        // base case 
        if(cur == null) return;
        // 先处理左节点
        dfs(cur.left);
        // 链接上一个结点
        if(pre != null) 
            pre.right = cur;
        else
        // 如果没有上一个节点，就把当前结点设为头结点
            head = cur;
        cur.left = pre;
        // 更新pre结点
        pre = cur;
        // 处理右节点
        dfs(cur.right);
        // 由于右节点是最后处理的，也是该部分数值最大的结点，每次都可以保证pre为该部分最后的结点
    }
}