[LeetCode] Flattern Binary Tree To LinkedList

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 

解题思路：

1. 如果root同时有left, right, 则把right存到stack

2. 如果root有left, 则将root.right = root.left,即将左子 树移到右子树

3. 如果root == null, 则从stack pop出一个，将此作为root的右子树

4. 每次都将root.right 作为新的root， repeat 1-4

Java Code:

 public void flatten(TreeNode root) {
        TreeNode p = root;
        Stack tmp = new Stack();
        
        while(p != null){ 
            
         if(p.right != null && p.left != null){
             tmp.add(p.right);
         }
         
         if(p.left != null){
             p.right = p.left;
             p.left = null;
         }
         
         if(p.right == null && !tmp.isEmpty()){
             p.right = tmp.pop();
         }
         
         p = p.right;
        }
    }