Flatten binary tree to linked list

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Solution I: using stack, pre order traversal

public class Solution {
    public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;

        while(p != null || !stack.empty()){

            if(p.right != null){
                stack.push(p.right);
            }

            if(p.left != null){
                p.right = p.left;
                p.left = null;
            }else if(!stack.empty()){
                TreeNode temp = stack.pop();
                p.right=temp;
            }

            p = p.right;
        }
    }
}

Solution II: in place

note the use of variable post

思路是先遍历右子树，然后左子树，最后根节点。这样的好处是遍历完一个子树后，子树里的所有左右孩子指针都不需要了。 递归调用返回该子树中第一个节点，用于后续调用的后继。

public class Solution {
  public void flatten(TreeNode root){
        if (root == null){
            return;
        }

        flat(root, null);
    }

    private TreeNode flat(TreeNode root, TreeNode post){
        if (root == null){
            return post;
        }
        TreeNode right = flat(root.right, post);
        TreeNode left = flat(root.left, right);
        root.right = left;
        root.left = null;
        return root;
    }
}