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

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        init_map(inorder);
        int left = 0;
        int right = inorder.size() - 1;
        int mid = node_idx[preorder[0]];
        int left_len = mid - left;
        int right_len = right - mid;

        TreeNode* root = new TreeNode(preorder[0]);
        root->left  = innerBuildTree(preorder, inorder, left, mid - 1, left + 1, left + left_len);
        root->right = innerBuildTree(preorder, inorder, mid + 1, right, left + left_len + 1, right);
        return root;
    }
private:
    unordered_map<int, int> node_idx;
    void init_map(vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); ++i) {
            node_idx[inorder[i]] = i;
        }
    }
    TreeNode* innerBuildTree(vector<int>& preorder, vector<int>& inorder, int left, int right, int pre_left, int pre_right) {
        if (left > right || pre_left > pre_right) {
            return nullptr;
        }

        int mid = node_idx[preorder[pre_left]];
        int left_len  = mid - left;
        int right_len = right - mid;
        TreeNode* node = new TreeNode(inorder[mid]);
        node->left  = innerBuildTree(preorder, inorder, left, mid - 1, pre_left + 1, pre_left + left_len);
        node->right = innerBuildTree(preorder, inorder, mid + 1, right, pre_left + left_len + 1, pre_right);
        return node;
    }
};