105. Construct Binary Tree from Preorder and Inorder Traversal

#105 Construct Binary Tree from Preorder and Inorder Traversal

Medium

给定二叉树的先序遍历与中序遍历，构建二叉树

Problem

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

<figure class="coding-figure">
<svg class="coding-tree" viewBox="0 0 275 240" width="250" role="img" aria-label="Binary tree: 3 is the root, 9 is its left child, 20 is its right child, and 20 has children 15 and 7">
<line class="edge" x1="110" y1="32" x2="40" y2="120"/>
<line class="edge" x1="110" y1="32" x2="180" y2="120"/>
<line class="edge" x1="180" y1="120" x2="125" y2="208"/>
<line class="edge" x1="180" y1="120" x2="235" y2="208"/>
<g class="node"><circle cx="110" cy="32" r="22"/><text x="110" y="32">3</text></g>
<g class="node"><circle cx="40" cy="120" r="22"/><text x="40" y="120">9</text></g>
<g class="node"><circle cx="180" cy="120" r="22"/><text x="180" y="120">20</text></g>
<g class="node"><circle cx="125" cy="208" r="22"/><text x="125" y="208">15</text></g>
<g class="node"><circle cx="235" cy="208" r="22"/><text x="235" y="208">7</text></g>
</svg>
</figure>

```text
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]


## Idea

Use divide and conquer.

The first element of `preorder` is always the root of the tree. Find the root in `inorder`: every value to its left belongs to the left subtree, and every value to its right belongs to the right subtree. This also tells us the size of the left subtree, `leftSize`.

In `preorder`, the root is followed by the whole left subtree and then the whole right subtree. So the `leftSize` values right after the root are the preorder of the left subtree, and the rest are the preorder of the right subtree.

Now each subtree has its own preorder and inorder sequences, so we can build it recursively in the same way. An empty range means an empty subtree.

```text
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

root = 3
inorder:   [9] 3 [15,20,7]    -> leftSize = 1
preorder:  3 [9] [20,15,7]

left subtree:   preorder = [9],       inorder = [9]
right subtree:  preorder = [20,15,7], inorder = [15,20,7]

Scanning inorder for the root every time takes \(O(n^2)\) in the worst case. Since all values are unique, store each value's index in inorder in a hash map first, so the root can be found in \(O(1)\). Also pass index ranges instead of copying subarrays.

Time complexity: \(O(n)\), Space complexity: \(O(n)\)

Pseudo-code

indexOf = empty hash map;

for (i = 0; i < length(inorder); i++) {
    indexOf[inorder[i]] = i;
}

return Build(0, 0, length(inorder) - 1);


// Builds the subtree whose preorder starts at preStart
// and whose inorder is inorder[inStart..inEnd].
Build(preStart, inStart, inEnd) {
    if (inStart > inEnd) {
        return null;
    }

    root = new TreeNode(preorder[preStart]);
    rootIndex = indexOf[root.value];
    leftSize = rootIndex - inStart;

    root.left = Build(preStart + 1, inStart, rootIndex - 1);
    root.right = Build(preStart + 1 + leftSize, rootIndex + 1, inEnd);

    return root;
}