Flatten Binary Tree to Linked List leetcode

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

这道题题意就是把树变成linkedlist 但是要以只有右子树的树形式表示出来
用先序遍历, 遍历到的值作为便利到的前一个点的右子树, 前一个点的左子树设为空.
因为递归右子树是在递归左子树之后, 所以root.right会发生变化, 所以root.right要单独存储起来. 便利一次 时间为O(n).

非递归解法就是遇到右子树就入栈， 然后把左子树变成自己的右子树， 左子树设空。 如果没有左子树了， 就从栈里拿出一个当当前node的右子树。

public class Solution {
    public void flatten(TreeNode root) {
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        res.add(null);
        helper(res, root);
    }
    public void helper(ArrayList<TreeNode> res, TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode right = root.right;
        if (res.get(0) != null) {
            res.get(0).right = root;
            res.get(0).left = null;
        }
        res.set(0, root);
        helper(res, root.left);
        helper(res, right);
    }
}
//非递归解法 推荐
public class Solution {
    public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        while(p != null || !stack.isEmpty()) {
            if (p.right != null) {
                stack.push(p.right);
            }
            if (p.left != null) {
                p.right = p.left;
                p.left = null;
            } else if (!stack.isEmpty()) {
                TreeNode tem = stack.pop();
                p.right = tem;
            }
            p = p.right;
        }
    }
}