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

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

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
（只對當(dāng)前點(diǎn)看忿族，每個當(dāng)前點(diǎn)一下都當(dāng)成N，因?yàn)槭且淮蝫hile總。要遍歷每個結(jié)點(diǎn)的while是在下面考慮的嘿悬，有n/2二分）
So， T(N) = 2T(N/2) + O(logN) => (logn)^2

Space Complexity: O(N) 遞歸緩存

Solution2：右側(cè)開始Post-order dfs

思路： 右側(cè)開始 regular 遞歸Post-order dfs，依次相連即可
Time Complexity: O(N) Space Complexity: O(N) 遞歸緩存

Screen Shot 2017-11-18 at 21.34.08.png

Solution3：

思路： 和Solution1思路相似决乎，將當(dāng)前結(jié)點(diǎn)cur的左樹直接插入到cur和cur.右樹之間，而不是去先排左樹(while找右下may cost O(N))派桩。
Mark: 應(yīng)該也有遞歸寫法构诚，還沒寫
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;
        }
    }
}