99. Recover Binary Search Tree
1. Description
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.
2. Example
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.
3. Constraints
- The number of nodes in the tree is in the range [2, 1000].
- $-2^{31}$ <= Node.val <= $2^{31} - 1$
4. Follow up
- A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?
5. Solutions
Morris Iteration
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
void recoverTree(TreeNode *root) {
traverse_(root);
swap(big_point_->val, small_point_->val);
}
private:
TreeNode *big_point_ = nullptr;
TreeNode *small_point_ = nullptr;
TreeNode *last_point_ = nullptr;
void traverse_(TreeNode *root) {
TreeNode *iter = root;
TreeNode *most_right = nullptr;
while (iter != nullptr) {
most_right = iter->left;
if (most_right != nullptr) {
while (most_right->right != nullptr && most_right->right != iter) {
most_right = most_right->right;
}
if (most_right->right == nullptr) {
most_right->right = iter;
iter = iter->left;
continue;
} else {
most_right->right = nullptr;
}
}
if (last_point_ !=nullptr && last_point_->val > iter->val) {
if(big_point_ == nullptr || big_point_->val < last_point_->val) {
big_point_ = last_point_;
}
if(small_point_ == nullptr || small_point_->val > iter->val) {
small_point_ = iter;
}
}
last_point_ = iter;
iter = iter->right;
}
}
};