leetcode

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

1382.cpp (1258B)

      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 *balanceBST(TreeNode *root) {
     10         vector<TreeNode *> nums;
     11 
     12         {
     13             stack<TreeNode *> st;
     14             while (true) {
     15                 while (root) {
     16                     st.push(root);
     17                     root = root->left;
     18                 }
     19                 if (st.empty()) break;
     20                 root = st.top(), st.pop();
     21                 nums.push_back(root);
     22                 root = root->right;
     23             }
     24         }
     25 
     26         stack<record> st;
     27         TreeNode *head = new TreeNode(INT_MIN), *t;
     28         st.push({head, 0, (int)nums.size() - 1});
     29         while (!st.empty()) {
     30             record r = st.top();
     31             st.pop();
     32             while (r.low <= r.high) {
     33                 int mid = r.low + (r.high - r.low) / 2;
     34                 nums[mid]->left = nums[mid]->right = nullptr;
     35                 (nums[mid]->val >= r.root->val ? r.root->right : r.root->left) = t = nums[mid];
     36                 st.push({r.root = t, mid + 1, r.high});
     37                 r.high = mid - 1;
     38             }
     39         }
     40         return head->right;
     41     }
     42 };