[LeetCode] 114. Flatten Binary Tree to Linked List

Posted on | In

Problem

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

For example, given the following tree:

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

The flattened tree should look like:

1
2
3
4
5
6
7
8
9
10
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Explanation 1

  1. The brute force solution is using pre-order traversal to store all elements to a list, then traversal the list’s elements and make each one’s left node to be null and right node to be its next node.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    void preorder(TreeNode root, List<TreeNode> lst) {
        if (root == null) return;
        lst.add(root);
        preorder(root.left, lst);
        preorder(root.right, lst);
    }
    public void flatten(TreeNode root) {
        if (root == null) return;
        List<TreeNode> lst = new ArrayList<>();
        preorder(root, lst);
        for (int i = 0; i < lst.size()-1; i++) {
            lst.get(i).left = null;
            lst.get(i).right = lst.get(i+1);
        }
        lst.get(lst.size()-1).left = null;
        lst.get(lst.size()-1).right = null;
    }
}

Explanation 2

  1. We usually can use recursion for tree problem. For example, if we already flattern the left subtree and the right subtree, which is illustrated below:

    1
    2
    3
    4
    5
    6
    7
             1
        /  \
       2    5
       \     \
        3     6 <- rightTail
         \
          4 <- leftTail

  2. Now, how do we make root, root.left, and root.right to be a flattern list?

    1
    2
    3
     leftTail.right = root.right;
 root.right = root.left;
 root.left = null;

  3. From the above illustration and code, we have used the already flattern list’s leftTail and rightTail. Therefore, the recursion’s base case is the flattern list’s tail node.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode helper(TreeNode root) {
        if (root == null) return null;
        TreeNode leftTail = helper(root.left);
        TreeNode rightTail = helper(root.right);
        if (leftTail != null) {
            leftTail.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        if (rightTail != null) return rightTail;
        if (leftTail != null) return leftTail;
        return root;
    }
    public void flatten(TreeNode root) {
        helper(root);
    }
}