力扣 剑指 Offer 36. 二叉搜索树与双向链表

二叉树的问题总是能给人惊(ma)喜(fan) 如果能想到关键点，那么就是很简单的一题 必须要想到：对于每一个节点我们应当把他的 左指针 指向 左子树变成的链表的尾节点（即左子树中最大的那个节点） 右指针 指向 右子树变成的链表的头节点（即右子树中最小的那个节点） 然后我们就可以写出递归方法了

class Solution {
          
   
    public Node treeToDoublyList(Node root) {
          
   
        if(root == null)
            return null;
        find(root);
        Node head = findHead(root);
        Node tail = findTail(root);
        head.left = tail;
        tail.right = head;
        return head;
    }
    void find(Node t){
          
   
        if(t.left != null){
          
   
            find(t.left);
            Node h = findTail(t.left);
            h.right = t;
            t.left = h;
        }
        if(t.right != null){
          
   
            find(t.right);
            Node h = findHead(t.right);
            h.left = t;
            t.right = h;
        }
    }
    Node findTail(Node t){
          
   
        if(t.right == null){
          
   
            return t;
        }
        return findTail(t.right);
    }
    Node findHead(Node t){
          
   
        if(t.left == null){
          
   
            return t;
        }
        return findHead(t.left);
    }
}

在题解中给出了一个更加简单但不好理解的代码 一般而言二叉树的递归我们一般都是先对左右子树递归处理，然后根据左右的结果处理根节点（即上面写的思路） 但这里不一样，是左 根 右 的顺序，他是根据左的结果处理根，再根据处理好的根来处理右，这样代码就短了很多，但时间复杂度没变，都是遍历了整棵树O(n)

class Solution {
          
   
    Node pre,head;
    public Node treeToDoublyList(Node root) {
          
   
        if(root == null)return root;
        dfs(root);
        head.left=pre;
        pre.right=head;
        return head ;
    }

    public void dfs(Node cur){
          
   
        if(cur==null)return;
        dfs(cur.left);
        if(pre==null)head = cur;
        else pre.right = cur;
        cur.left = pre ;
        pre = cur ;
        dfs(cur.right);
        return ;
    }
}