/ Data Structure and Algorithms  

Leetcode 114. Flatten Binary Tree to Linked List

Question



Expand a binary tree into a linked list.

Similar Question

Solution

It can be found that the order of flatten is actually the pre-order traversal of the binary tree. So the problem is actually to convert the binary tree through the right pointer to form a linked list.

E.g. given:

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

Try to get:

1
1 -> 2 -> 3 -> 4 -> 5 -> 6

Once we have this pre-order list, we can tranverse through it. Each time a node is traversed, the right pointer of the previous node is updated to the current node.

The pre-order list is 1 2 3 4 5 6.

Traverse to 2 and point the right pointer of 1 to 2. 1-> 2 3 4 5 6.

Traverse to 3 and point the right pointer of 2 to 3. 1-> 2-> 3 4 5 6.

…

Because we saved the right child with the list, there is no need to worry about the right child being lost.

Code:

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
29
30
31
32
public void flatten(TreeNode root) {
    // store the pre-order list
    Queue<Integer> preOrder = new LinkedList<>();

    // get the preorder list of the tree
    preOrder(root, preOrder);

    TreeNode current = root;
    preOrder.poll();

    // traverse the list
    while (!preOrder.isEmpty()) {
        TreeNode newNode = new TreeNode(preOrder.poll());

        // left node always null
        current.left = null;
        current.right = newNode;

        current = newNode;
    }
}

// pre order traverse
private void preOrder(TreeNode root, Queue<Integer> preOrder) {
    if (root == null) {
        return;
    }

    preOrder.offer(root.val);
    preOrder(root.left, preOrder);
    preOrder(root.right, preOrder);
}