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

思路: 用Stack,如果当前节点有右子树,把右子树入栈,左子树放到右子树,如果找到左子树叶子节点,左子树叶子节点接到stack中pop出来的右子树节点。
复杂度: Time O(n), Space O(n)

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
           if (cur.right != null) { // 右子树放到stack
               stack.push(cur.right);
           }
           if (cur.left != null) { // 如果右左子树,左子树变为右子树
               cur.right = cur.left;
               cur.left = null; // 原来左子树为null
           } else if (!stack.isEmpty()) { // 找到左子树的叶子
               TreeNode temp = stack.pop(); 
               cur.right = temp;
           }
           cur = cur.right;
        }
    }
}