Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 19

Description

Recover Binary Search Tree

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Example 1:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

Constraints:

• The number of nodes in the tree is in the range [2, 1000].
• -231 <= Node.val <= 231 - 1

Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {    
  vector<TreeNode*> wrongNodes;
  void check(TreeNode* cur, TreeNode* prev) {
    if(prev && prev->val >= cur->val) {
      wrongNodes.push_back(prev);
      wrongNodes.push_back(cur);
    }
  }
public:
  void recoverTree(TreeNode* root) {
    TreeNode *cur = root, *prev = nullptr;
    while(cur) {
      if(!(cur->left)) {
        check(cur, prev);
        prev = cur;
        cur = cur->right;
      } else {
        TreeNode *pred = cur->left;
        while(pred->right && pred->right != cur) pred = pred->right;
        if(pred->right) {
          pred->right = nullptr;
          check(cur, prev);
          prev = cur;
          cur = cur->right;
        } else {
          pred->right = cur;
          cur = cur->left;
        }
      }
    }
    swap(wrongNodes.front()->val, wrongNodes.back()->val);
  }
};

// Accepted
// 1919/1919 cases passed (20 ms)
// Your runtime beats 98.38 % of cpp submissions
// Your memory usage beats 35.12 % of cpp submissions (58 MB)