Flatten Binary Tree to Linked List

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

Hint: we first provide an obvious method, a recursion version. The idea behind it is to use the pre-order traversal of a binary tree.

Java语言: FlattenBinaryTree

01 public void flatten(TreeNode root) {
02     if(root==null)
03         return;
04     if(root.left!=null)
05     {
06         TreeNode rChild=root.right;
07         root.right=root.left;
08         root.left=null;
09         TreeNode rightMost=root.right;
10         while(rightMost.right!=null)
11         {
12             rightMost=rightMost.right;
13         }
14         rightMost.right=rChild;          
15     }
16   
17     flatten(root.right);      
18 }

Consider how the pre-order traversal is accomplished inside? We may use a stack to to so.

01 import java.util.*;
02 public class Solution {
03     public void flatten(TreeNode root) {
04         if(root==null)
05             return;
06               
07         TreeNode curr=null;
08         Stack<TreeNode> trees=new Stack<TreeNode>();
09         trees.add(root);
10         while(!trees.empty())
11         {
12             TreeNode parent=trees.pop();
13               
14             if(parent.right!=null)
15             {
16                 trees.push(parent.right);
17             }
18           
19             if(parent.left!=null)
20             {
21                 trees.push(parent.left);
22             }
23             parent.left=null;
24             parent.right=null;
25             if(root==parent)
26             {                                              
27                 curr=parent;
28             }
29             else
30             {              
31                 curr.right=parent;
32                 curr=curr.right;
33             }
34         }
35       
36     }
37 }