leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0108.cpp (805B)

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 };