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

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

这里我直接新建了一个tree。代替原来的。注意必须在最后修改root的指针指向的地方，而不是修改root。（值的传递）

1 /** 2  * Definition for binary tree 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public void flatten(TreeNode root) {12         // Start typing your Java solution below13         // DO NOT write main() function14         if(root == null) return;15         TreeNode r = new TreeNode(root.val);16         Stack
      
        s = new Stack
       
        ();17         s.push(root);18         TreeNode ts = r;19         while(s.empty() != true){20             TreeNode cur = s.pop();21             if(cur.right != null)22             s.push(cur.right);23             if(cur.left != null)24             s.push(cur.left);25             ts.right = new TreeNode(cur.val);26             ts = ts.right;27         }28         root.right = r.right.right;29         root.left = null;30     }31 }
       
      

方法二： 直接修改原来的树。

We can notice that in the flattened tree, each sub node is the successor node of it’s parent node in the pre-order of the original tree. So, we can do it in recursive manner, following the steps below:

1.if root is NULL return;

2.flatten the left sub tree of root, if there is left sub-tree;

3.flatten the right sub-tree of root, if has;

4.if root has no left sub-tree, then root is flattened already, just return;

5.we need to merge the left sub-tree with the right sub-tree, by concatenate the right sub-tree to the last node in left sub-tree.

5.1.find the last node in the left sub tree, as the left is flattened, this is easy.

5.2.concatenate the right sub-tree to this node’s right child.

5.3.move the left sub-tree to the right for root.

5.4.clear the left child of root.

6.done.

1 A much simpler solution. 2 public class Solution { 3 public void flatten(TreeNode root) { 4 // Start typing your Java solution below 5 // DO NOT write main() function 6 preOrder(root, null); 7 return; 8 } 9 10 public static TreeNode preOrder(TreeNode root, TreeNode prev) {11 if (root == null) return null;12 13 TreeNode leftNode = root.left;14 TreeNode rightNode = root.right;15 16 if (prev == null) {17 prev = root;18 } else {19 prev.left = null;20 prev.right = root;21 prev = root;22 }23 24 if (leftNode != null) {25 prev = preOrder(leftNode, prev);26 }27 if (rightNode != null) {28 prev = preOrder(rightNode, prev);29 }30 return prev;31 }32 }

 第二遍：

1 public class Solution { 2     public void flatten(TreeNode root) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         if(root == null) return; 6         LinkedList
      
        queue = new LinkedList
       
        (); 7         TreeNode result = null; 8         queue.push(root); 9         while(queue.size() != 0){10             TreeNode tmp = queue.pop();11             if(tmp.right != null) queue.push(tmp.right);12             if(tmp.left != null) queue.push(tmp.left);13             if(result == null) result = tmp;14             else{15                 result.right = tmp;16                 result = result.right;17             }18             result.left = result.right = null;19         }20     }21 }
       
      

采用stack做preorder search。 存一个current list的tail指针， 更新这个指针。