leetcode

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

0099.cpp (618B)

      1 class Solution {
      2   public:
      3     void recoverTree(TreeNode *root) {
      4         stack<TreeNode *> st;
      5         TreeNode *head = root, *prev = new TreeNode(INT_MIN), *l1 = nullptr, *l2 = nullptr;
      6         while (true) {
      7             while (root) {
      8                 st.push(root);
      9                 root = root->left;
     10             }
     11             if (st.empty()) break;
     12             root = st.top(), st.pop();
     13             if (root->val < prev->val) {
     14                 if (!l1) l1 = prev;
     15                 l2 = root;
     16             }
     17             prev = root;
     18             root = root->right;
     19         }
     20         swap(l1->val, l2->val);
     21     }
     22 };