leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0108.cpp (805B)

      1 class Solution {
      2     struct record {
      3         TreeNode *root;
      4         int low, high;
      5         record(TreeNode *root, int low, int high) : root(root), low(low), high(high) {}
      6     };
      7 
      8   public:
      9     TreeNode *sortedArrayToBST(vector<int> &nums) {
     10         stack<record> st;
     11         TreeNode *head = new TreeNode(INT_MIN), *t;
     12         st.push({head, 0, (int)nums.size() - 1});
     13         while (!st.empty()) {
     14             record r = st.top();
     15             st.pop();
     16             while (r.low <= r.high) {
     17                 int mid = r.low + (r.high - r.low) / 2;
     18                 (nums[mid] >= r.root->val ? r.root->right : r.root->left) = t = new TreeNode(nums[mid]);
     19                 st.push({r.root = t, mid + 1, r.high});
     20                 r.high = mid - 1;
     21             }
     22         }
     23         return head->right;
     24     }
     25 };