LCOF36

[underwindfall]

• https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

• 思路

  • dfs
  • inorder

• [x] 刷15mins

• [x] 刷5mins

// time O(n)
    // space O(n)
    Node head = null, pre = null;

    public Node treeToDoublyList(Node root) {  
        if (root == null) return root;
        inOrder(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    void inOrder(Node node) {
        if(node == null) {
            return;
        }
        inOrder(node.left);
        if (pre == null) {
            head = node;
        } else {
            pre.right = node;
            node.left = pre;
        }
        pre = node;
        inOrder(node.right);
    }