Maximum Binary Tree 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
  TreeNode *constructMaximumBinaryTree(vector<int> &nums) {
16
    return recur(0, nums.size() - 1, nums);
17
  }
18

19
  TreeNode *recur(int st, int en, vector<int> &ar) {
20
    if (st > en) {
21
      return NULL;
22
    }
23
    TreeNode *cur = new TreeNode();
24
    int maxm = -1, ind;
25
    for (int i = st; i <= en; i++) {
26
      if (maxm < ar[i]) {
27
        maxm = ar[i];
28
        ind = i;
29
      }
30
    }
31

32
    cur->val = ar[ind];
33
    cur->left = recur(st, ind - 1, ar);
34
    cur->right = recur(ind + 1, en, ar);
35

36
    return cur;
37
  }
38
};