leetcode

0 class Solution {

1 struct record {

2 TreeNode *root;

3 int low, high;

4 record(TreeNode *root, int low, int high) : root(root), low(low), high(high) {}

5 };

6

7 public:

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

9 stack<record> st;

10 TreeNode *head = new TreeNode(INT_MIN), *t;

11 st.push({head, 0, (int)nums.size() - 1});

12 while (!st.empty()) {

13 record r = st.top();

14 st.pop();

15 while (r.low <= r.high) {

16 int mid = r.low + (r.high - r.low) / 2;

17 (nums[mid] >= r.root->val ? r.root->right : r.root->left) = t = new TreeNode(nums[mid]);

18 st.push({r.root = t, mid + 1, r.high});

19 r.high = mid - 1;

20 }

21 }

22 return head->right;

23 }

24 };