Construct Binary Tree from Preorder and Inorder Traversal LeetCode solution in C++

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 * int val;
5
 * TreeNode *left;
6
 * TreeNode *right;
7
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10
 * right(right) {}
11
 * };
12
 */
13
class Solution {
14
 public:
15
  typedef vector<int>::iterator vecIt;
16

17
  TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder, TreeNode *retNode, vecIt startIt,
18
                      vecIt endIt) {
19
    if (startIt >= endIt) return (NULL);
20
    vecIt rootIt;
21
    vecIt midIt;
22
    int rootVal;
23

24
    rootIt = preorder.begin();
25
    rootVal = *rootIt;
26
    preorder.erase(rootIt);
27
    retNode = new TreeNode(rootVal);
28
    midIt = find(startIt, endIt, rootVal);
29
    retNode->left = buildTree(preorder, inorder, retNode->left, startIt, midIt);
30
    retNode->right = buildTree(preorder, inorder, retNode->right, midIt + 1, endIt);
31
    return (retNode);
32
  }
33
  TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
34
    TreeNode *retNode;
35

36
    return (buildTree(preorder, inorder, retNode, inorder.begin(), inorder.end()));
37
  }
38
};