Construct Binary Tree from Preorder and Inorder Traversal

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:

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]

Constraints:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder consist of unique values.
Each value of inorder also appears in preorder.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    const inMap = {};
    inorder.forEach((val, index) => {
        inMap[val] = index;
    });
    return construct(preorder, inorder, 0, inorder.length - 1, 0, inMap);
};

var construct = function(preorder, inorder, start, end, rootIndex, inMap) {
    if (start > end || rootIndex >= preorder.length) {
      return null;
    }

    const root = new TreeNode(preorder[rootIndex]);
    const split = inMap[root.val];
    const shift = split - start; // number of nodes of left subtree

    root.left = construct(preorder, inorder, start, split - 1, rootIndex + 1, inMap);
    root.right = construct(preorder, inorder, split + 1, end, rootIndex + shift + 1, inMap);

    return root;
};

We will implement a DFS solution. We know the first value in preorder must be the root of the tree. Finding the root value in inorder gives us the left and right halves of the two subtrees. Next, split up the tree into subtrees and recursively construct the full tree.

For example, say preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7]. In our first call, the root is 3 (first value of preorder), so we split up inorder at that value. Thus, for our two recursive calls, we use inorder = [9] and inorder = [15, 20, 7]. We do a similar operation to preorder without the first value, by splitting it into two groups of the same size as inorder. In this case, we get preorder = [9] and preorder = [20, 15, 7]. Note that, in the implementation we just keep track of all the indices instead of splitting the array.

Problem​

Solution​

Problem

Solution