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

For example,
Given

         1
        /        2   5
      / \        3   4   6

   1
         2
             3
                 4
                     5
                         6

click to show hints.

空间消耗比较大，非in-place的解法。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if(root==null) return;
        ArrayList<TreeNode> a=new ArrayList<TreeNode>();
        prevOrder(root,a);
        for(int i=0;i<a.size()-1;i++){
            a.get(i).left=null;
            a.get(i).right=a.get(i+1);
        }
    }
    public void prevOrder (TreeNode root,List<TreeNode> a){
        if(root==null) return;
        a.add(root);
        prevOrder(root.left,a);
        prevOrder(root.right,a);
    }
}

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if(root==null) return;
        while(root!=null){
            if(root.left!=null){
                TreeNode node=root.left;
                while(node.right!=null) node=node.right;
                node.right=root.right;
                root.right=root.left;
                root.left=null;
            }
            root=root.right;
        }
    }
}