105. Construct Binary Tree from Preorder and Inorder Traversal

Posted on Edited on In

105. Construct Binary Tree from Preorder and Inorder Traversal

Description

Difficulty: Medium

Related Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree

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:

1
2
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

1
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.

Hints/Notes

Solution

Language: C++

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
38
39
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> valToIndex;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int size = preorder.size();
        for (int i = 0; i < size; i++) {
            valToIndex[inorder[i]] = i;
        }
        return build(preorder, 0, size - 1, inorder, 0, size - 1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                    vector<int>& inorder, int inStart, int inEnd) {
        if (preStart > preEnd) {
            return nullptr;
        }
        int rootVal = preorder[preStart];
        TreeNode* root = new TreeNode(rootVal);
        int inorderIndex = valToIndex[rootVal];
        int leftSize = inorderIndex - inStart;
        root->left = build(preorder, preStart + 1, preStart + leftSize,
                           inorder, inStart, inorderIndex - 1);
        root->right = build(preorder, preStart + leftSize + 1, preEnd,
                            inorder, inorderIndex + 1, inEnd);
        return root;
    }
};