Construct Binary Tree from Preorder and Inorder Traversal

Description

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

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

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution

preorder traversal of root = [root->val, preorder traversal of root->left, preorder traversal of root->right].

inorder traversal of root = [inorder traversal of root->left, root->val, inorder traversal of root->right].

Since there are no duplicates, we can use a hash table to quickly get the index of root->val in the inorder traversal of root, denoted as rootIdx. Then the preorder traversal of root-left is preorder[1:rootIdx], including preorder[rootIdx].

Then we just need to solve two smaller problems.

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        unordered_map<int, int> hash;
        for (int i = 0; i < inorder.size(); ++i) {
            int val = inorder[i];
            hash[val] = i;
        }
        return buildTree(
            preorder, 0, preorder.size(),
            inorder, 0, inorder.size(),
            hash);
    }

    TreeNode *buildTree(
        vector<int> &preorder, int l1, int r1,
        vector<int> &inorder, int l2, int r2, unordered_map<int, int> &hash) {
        if (l1 >= r1)
            return nullptr;
        int rootVal = preorder[l1];
        int rootIdx = hash[rootVal];
        TreeNode *root = new TreeNode(rootVal);
        int leftLen = rootIdx - l2;
        root->left = buildTree(
            preorder, l1 + 1, l1 + 1 + leftLen,
            inorder, l2, rootIdx,
            hash);
        root->right = buildTree(
            preorder, l1 + 1 + leftLen, r1,
            inorder, rootIdx + 1, r2,
            hash);
        return root;
    }
};