leetcode

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

0669.cpp (1037B)

      1 class Solution {
      2   public:
      3     TreeNode *trimBST(TreeNode *root, int low, int high) {
      4         if (!root) return nullptr;
      5         while (root) {
      6             if (root->val < low)
      7                 root = root->right;
      8             else if (root->val > high)
      9                 root = root->left;
     10             else
     11                 break;
     12         }
     13         stack<pair<TreeNode *, TreeNode **>> st;
     14         TreeNode *head = root, **link = nullptr;
     15         while (true) {
     16             while (root) {
     17                 if (root->val < low)
     18                     root = *link = root->right;
     19                 else if (root->val > high)
     20                     root = *link = root->left;
     21                 else {
     22                     if (root->right) st.push({root->right, &root->right});
     23                     link = &root->left;
     24                     root = root->left;
     25                 }
     26             }
     27             if (st.empty()) break;
     28             root = st.top().first;
     29             link = st.top().second;
     30             st.pop();
     31         }
     32         return head;
     33     }
     34 };