114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.
For example,
Given

The flattened tree should look like:

Solution1： regular 递归Post-order dfs

思路：regular 递归 Post-order dfs，将排好的左树插入node 和排好的右树之间。
Time Complexity:
(1) Worst: O(N^2)
Ex. 只有左树一条线的情况

(2) Average(when nearly balanced): (logn)^2
如果是nearly balanced的 while找右下是 O(深度) = logn
（只对当前点看，每个当前点一下都当成N，因为是一次while总。要遍历每个结点的while是在下面考虑的，有n/2二分）
So， T(N) = 2T(N/2) + O(logN) => (logn)^2

Space Complexity: O(N) 递归缓存

Solution2：右侧开始Post-order dfs

思路： 右侧开始 regular 递归Post-order dfs，依次相连即可
Time Complexity: O(N) Space Complexity: O(N) 递归缓存

Screen Shot 2017-11-18 at 21.34.08.png

Solution3：

思路： 和Solution1思路相似，将当前结点cur的左树直接插入到cur和cur.右树之间，而不是去先排左树(while找右下may cost O(N))。
Mark: 应该也有递归写法，还没写
Time Complexity: O(N) Space Complexity: O(N)

屏幕快照 2017-09-06 下午5.57.32.png

Solution1 Code：

class Solution1 {
    public void flatten(TreeNode root) {
        if (root == null) return;
        
        flatten(root.left);
        flatten(root.right);
        
        // insert root.left to between root and root.right
        TreeNode save_right = root.right;
        root.right = root.left;
        
        TreeNode cur = root;
        while (cur.right != null) cur = cur.right;
        cur.right = save_right;
        
        root.left = null;
    }
}

Solution2 Code：

class Solution2 {
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null)
            return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
}

Solution3 Code：

class Solution3 {
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.left != null) {
                // insert cur.left_subtree into between cur and cur.right_subtree
                TreeNode pre = cur.left;
                while(pre.right != null) pre = pre.right; // find the right bottom of cur.left 
                // insert 
                pre.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}