Flatten Binary Tree to Linked List

 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     TreeNode newTree = null;
12     
13     public void flatten(TreeNode root) {
14         if(null == root)
15             return;
16         preOrder(root);
17         root.right = newTree.right;
18         root.left = null;
19     }
20     
21     /**
22      *     前序遍历一棵树，生成一棵只有右子树的树
23      * @param root
24      * @return
25      */
26     public void preOrder(TreeNode root){
27         if(null != root){
28             if(newTree == null){                        //新树的根节点如果为空
29                 newTree = new TreeNode(root.val);
30             }    
31             else{                                        //根节点不为空
32                 TreeNode temp = newTree;
33                 
34                 while(temp.right != null)
35                     temp = temp.right;                    //找到插入点
36                 temp.right = new TreeNode(root.val);    //在右子树插入结点                
37             }
38             preOrder(root.left);                        //遍历左子树
39             preOrder(root.right);                        //遍历右子树
40         }
41     }
42 }