Flatten Binary Tree to Linked List

Q：
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

A：
就是，只用right指针来指向下一个。
-----------------recursively 调用----------------------

public class FlattenBinaryTreeToLinkedList {
  public void flatten(TreeNode root) {
    flatten(null,root);
  }
  private TreeNode helper(TreeNode preNode, TreeNode root ){
      // use a preNode to record the the last added node in 
        if(root == null)
            return null;
        if(preNode != null){
            preNode.left = null;
            preNode.right = root;
        }
        preNode = root;
        TreeNode tmpRight = root.right; // coz root.right might be changed
        // add left
        if(root.left != null)
            preNode = helper(preNode, root.left);
        if(tmpRight != null)
            preNode = helper(preNode,tmpRight);
      return preNode;
  }
}

----------------------把通过preNode的传递的参数，换成类变量。 不提倡，软件工程方面差-----------

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

*****************每次返回最后一个node，并接上 尾巴即可 ******************

public class Solution {
    public void flatten(TreeNode root) {
        helper(root);
    }
    private TreeNode helper(TreeNode root){ // each return the right most node
        if(root == null)
            return null;
        TreeNode tail = root, r = root.right, l = root.left;
        root.left = null;
        if( l != null ){
            root.right = l;
            tail = helper(l);
        }
        if( r != null ){
            tail.right = r;
            tail = helper(r);
        }
        return tail;
    }
}
 

--------------------用一个stack 保存前序遍历的结果，并调整。

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

        // use a stack to remember to be vistied right child
        // following two ways to declare a stack works.
        // LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        Stack<TreeNode> stack = new Stack<TreeNode>();

        stack.push(root);
        TreeNode preNode = null;
        while (!stack.isEmpty()) {
            TreeNode curNode = stack.pop();
            if (preNode != null) {
                preNode.left = null;
                preNode.right = curNode;
            }
            if (curNode.right != null)
                stack.push(curNode.right);
            if (curNode.left != null)
                stack.push(curNode.left);
            preNode = curNode;
        }
    }
}

Mistakes:
1: 开始，没有加JustedAddedNode.left == null
     如果不加的话， 其节点总是保留着， 是不对的。呵呵, 第二遍的时候，又犯了这个错误！！！
2： 用stack存储的话，记得先把左右两边push进去，再更改current node的左右值。