Construct Binary Tree from Preorder and Postorder 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
  bool vis[40];
16

17
  TreeNode *solve(vector<int> &pre, int p, vector<int> &pos, int q) {
18
    TreeNode *root = new TreeNode(pre[p]);
19
    vis[pre[p]] = true;
20
    p++;
21
    q--;
22

23
    if (p >= pre.size() || q < 0) {
24
      return root;
25
    }
26
    if (!vis[pre[p]]) {
27
      int x = q;
28
      while (x > 0 and pos[x] != pre[p]) x--;
29
      if (pos[x] == pre[p]) {
30
        root->left = solve(pre, p, pos, x);
31
      }
32
    }
33
    if (!vis[pos[q]]) {
34
      int x = p;
35
      while (x < pre.size() - 1 and pos[q] != pre[x]) x++;
36
      if (pos[q] == pre[x]) {
37
        root->right = solve(pre, x, pos, q);
38
      }
39
    }
40
    return root;
41
  }
42

43
  TreeNode *constructFromPrePost(vector<int> &preorder, vector<int> &postorder) {
44
    int n = postorder.size();
45
    return solve(preorder, 0, postorder, n - 1);
46
  }
47
};