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

 

Hints:

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

这题思路：将左子树变成这样，将右子树变成这样，将转换后的右子树先放一边，将转换后的左子树变成根节点的右子树，然后再将前面的右子树添加到这个最右边（遍历到最后再加）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if(root==null) return ;
       flatten(root.left);//左子树转换
        flatten(root.right);//右子树转换
        
        TreeNode tmp=root.right;//将右子树取出
        root.right=root.left;//将左子树变成根节点的右子树
        root.left=null;//左子树置为Null
        //从根节点开始遍历，一直遍历到最右边节点，然后将上面的tmp加到这个右边。必须从根节点开始，因为左子树可能为空，变成右子树后右子树为空。
        TreeNode cur=root;
        while(cur.right!=null)
            cur=cur.right;
        cur.right=tmp;
        
    }
}