114. 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

重要：下面这几行就可以看出inorder，preorder 和 postorder

public void flatten(TreeNode root) {
    if (root==null) return;
    //加在这就是reorder
    flatten(root.left);
    //加在这就是inorder
    flatten(root.right);
    //加在这就是postorder
}

思路1：postorder思想：(a)flatten left subtree，(b)flatten right subtree, (c)concatenate root -> left flatten subtree -> right flatten subtree

public class Solution {
    public void flatten(TreeNode root) {
        if (root==null) return;
        flatten(root.left);
        flatten(root.right);

        // save current right for concatination
        TreeNode right = root.right;

        if (root.left!=null){
             // step 1: concatinate root with left flatten subtree
            root.right = root.left;
            root.left = null;
            // step 2: move to the end of new added flatten subtree
            while(root.right!=null){
                root = root.right;
            }
            // step 3: contatinate left flatten subtree with flatten right subtree    
            root.right = right;
        }
    }
}

思路2：用stack寸所有右节点

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 tmp = stack.pop();
                p.right = tmp;
            }

            p = p.right;
        }
    }
}