453.Flatten Binary Tree to Linked List

1.Description(Easy)

Flatten a binary tree to a fake "linked list" in pre-order traversal.

Here we use the_right_pointer in TreeNode as the _next _pointer in ListNode.

Notice

Don't forget to mark the left child of each node to null. Or you will get Time Limit Exceeded or Memory Limit Exceeded.

Example

              1
               \
     1          2
    / \          \
   2   5          3
  / \   \          \
 3   4   6          4
                     \
                      5
                       \
                        6

2.Code

用一个栈存放顺序每次放进去就peek出来，再依次放出来连接。别忘了把left设置成null.如果是最后把right设置成null.

public void flatten(TreeNode root){
    if(root==null){
        return;
    }
    Stack<TreeNode> st=new Stack<TreeNode>();
    st.push(root);
    while(!st.empty()){
        TreeNode node=st.pop();
        if(node.right!=null){
            st.push(node.right);
        }
        if(node.left!=null){
            st.push(node.left);
        }

        //connect
        node.left=null; //every node left is null;
        if(!st.empty()){
            node.right=st.peek(); //only peek.
        }else{
            node.right=null;
        }
    }
}