114. Flatten Binary Tree to Linked List

Problem:

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

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

4/30/2018 update:

Analysis: 
Divide and conquer. Flat left and right child trees first. Flattened left child tree is root's right. The flattened right child tree has to connect to the right most node of root and flattened left combined. Remember to set root's left to null.
Solution:

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        if (root.left != null) flatten(root.left);
        if (root.right != null) flatten(root.right);
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = null;
        while(root.right != null) {
            root = root.right;
        }
        root.right = temp;
    }
} 

------------------------------------------------------------------------------------------------------------------------
思路：
自我感觉preorder traversal比DC好理解一些。DC判断条件太复杂不容易想到。

DC解法：递归返回的是lastNode，需要获取左右子树的最后一个node。然后再flatten。flatten过后进行如下操作：

 if (rightLast != null) {  
       return rightLast;  
     }  
     if (leftLast != null) {  
       return leftLast;  
     }  
     return root;  

如果flatten过后的tree存在rightLast，那么马上返回。如果不存在rightlast 存在leftLast，证明root没有right child。返回leftLast就好。最后返回root的情况是root没有child。

实现：
在递归的时候，root.right要先保存起来。因为很有可能在flatten(root.left)的时候，root.right被替换掉了。