114. Flatten Binary Tree to Linked List

114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

My Solutions:

class Solution {
    
    //recursive
//     private TreeNode lastNode = null;
    
//     public void flatten(TreeNode root) {
//         if (root == null) return;
//         if (lastNode != null) {
//             lastNode.left = null;
//             lastNode.right = root;
//         }
//         lastNode = root;
//         TreeNode right = root.right;
//         flatten(root.left);
//         flatten(right);
        
//     }

    //iterative    
    //需要把node从小到大排列，所以先把right压栈，再把left压栈，pop时left先出栈
    
    public void flatten(TreeNode root) {
        if (root == null) return;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
            node.left = null;
            if (!stack.isEmpty()) {
                node.right = stack.peek();
            } else {
                node.right = null;
            }
        }
    }
    
}