99 Recover Binary Search Tree¶
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example 1:
Example 2:
Follow up:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
Solution: Inorder traversal¶
Using inorder traversal to find two nodes that have val < prev.val
Time complexity: O(n) Space complexity: O(h)
class Solution {
public:
void recoverTree(TreeNode *root) {
inorder(root);
swap(first->val, second->val);
}
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left);
if (prev && prev->val > root->val) {
if (!first) first = prev;
second = root;
}
prev = root;
inorder(root->right);
}
private:
TreeNode* first;
TreeNode* second;
TreeNode* prev;
};