114. Flatten Binary Tree to Linked List

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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

Code

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

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            if(curr.right != null) stack.push(curr.right);
            if(curr.left != null) stack.push(curr.left);

            if(!stack.isEmpty()) {
                curr.right = stack.peek();
            }

            curr.left = null;
        }
    }
}

class Solution {
    TreeNode prev = null;
    public void flatten(TreeNode root) {
        if(root == null) return;
        // 先处理右边node
        flatten(root.right);
        flatten(root.left);
        // 连接node
        root.right = prev;
        root.left = null;
        prev = root;
    }
}