| 26 | } |
| 27 | |
| 28 | TreeNode* buildSubtree(int left, int right, std::vector<int>& preorder, std::vector<int>& inorder, |
| 29 | int& preorderIndex, std::unordered_map<int, int>& inorderIndexesMap) { |
| 30 | // Base case: if no elements are in this range, return nullptr. |
| 31 | if (left > right) { |
| 32 | return nullptr; |
| 33 | } |
| 34 | int val = preorder[preorderIndex]; |
| 35 | // Set 'inorder_index' to the index of the same value pointed at by |
| 36 | // 'preorder_index'. |
| 37 | int inorderIndex = inorderIndexesMap[val]; |
| 38 | TreeNode* node = new TreeNode(val); |
| 39 | // Advance 'preorder_index' so it points to the value of the next |
| 40 | // node to be created. |
| 41 | preorderIndex++; |
| 42 | // Build the left and right subtrees and connect them to the current |
| 43 | // node. |
| 44 | node->left = buildSubtree(left, inorderIndex - 1, preorder, inorder, preorderIndex, inorderIndexesMap); |
| 45 | node->right = buildSubtree(inorderIndex + 1, right, preorder, inorder, preorderIndex, inorderIndexesMap); |
| 46 | return node; |
| 47 | } |