/ Data Structure and Algorithms  

Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal

Question



Restored binary tree according to the pre-order and in-order traversal.

Similar Question

Solution

The order of the pre-order traversal is the root node, the left subtree, and the right subtree. The order of the in-order traversal is the left subtree, the root node, and the right subtree.

So we just need to get the root node according to the pre-order traversal, and then find the position of the root node in the in-order traversal. The left side is the nodes of the left subtree, and the right is the nodes of the right subtree.

The left and right subtrees can then be generated recursively.

For example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
First find root node from pre-order, which is 3

Then split in-order into left subtree and right subtree
    Left:
        in-order [9]
    Right
        in-order [15,20,7]

Add in subarray in pre-order
    Left
        pre-order [9] 
        in-order  [9]
    Right
        pre-order [20 15 7] 
        in-order  [15,20,7]

Now we just need to build left subtree and right subtree, which turns original problem into a smaller one

Repeat above steps, until pre-order and in-order are empty, then return null

In fact, we don’t need to really split the pre-order and in-order, we just need to use two pointers to point to the beginning and end respectively. Note that the range of the array pointed to by the two pointers below includes the left boundary, not includes the right boundary.

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
33
34
35
36
37
public static TreeNode buildTree(int[] preorder, int[] inorder) {
    // map of value -> index in inorder array, for fast access
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }

    return getTree(preorder, 0, preorder.length, inorder, 0, inorder.length, map);
}

private static TreeNode getTree(int[] preOrder, int preOrderStart, int preOrderEnd,
                                int[] inOrder, int inOrderStart, int inOrderEnd,
                                Map<Integer, Integer> map) {
    if (preOrderStart == preOrderEnd) {
        return null;
    }

    // get root node value from preOrder
    int rootVal = preOrder[preOrderStart];
    // find the index of root node in inorder
    int rootIndex = map.get(rootVal);

    // number of nodes in left tree
    int leftNumber = rootIndex - inOrderStart;

    TreeNode node = new TreeNode(rootVal);

    // recursively construct left tree
    node.left = getTree(preOrder, preOrderStart + 1, preOrderStart + leftNumber + 1,
            inOrder, inOrderStart, rootIndex, map);

    // construct right tree
    node.right = getTree(preOrder, preOrderStart + leftNumber + 1, preOrderEnd,
            inOrder, rootIndex + 1, inOrderEnd, map);

    return node;
}