leetcode

0 class Solution {

1 struct record {

2 TreeNode **parent;

3 int start, end;

4 record(TreeNode **p, int s, int e) : parent(p), start(s), end(e) {}

5 };

6

7 public:

8 TreeNode *constructMaximumBinaryTree(vector<int> &nums) {

9 TreeNode *head, tmp;

10 stack<record> st;

11

12 head = new TreeNode(-1);

13 st.push({&head->right, 0, (int)nums.size()});

14 while (!st.empty()) {

15 auto [root, start, end] = st.top();

16 st.pop();

17 while (start < end) {

18 int index = -1;

19 for (int i = start, maxi = INT_MIN; i < end; i++)

20 if (nums[i] > maxi) {

21 maxi = nums[i];

22 index = i;

23 }

24 *root = new TreeNode(nums[index]);

25 st.push({&(*root)->left, start, index});

26 root = &(*root)->right;

27 start = index + 1;

28 }

29 }

30 return head->right;

31 }

32 };