99. Recover Binary Search Tree
99. Recover Binary Search Tree
cofama 发表于9个月前
99. Recover Binary Search Tree
• 发表于 9个月前
• 阅读 2
• 收藏 0
• 评论 0

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

``````class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode* prev = NULL;
TreeNode* tmp = NULL;
TreeNode* first = NULL;
TreeNode* second = NULL;
while(root!=NULL) {
if(root->left!=NULL) {
tmp = root->left;
while(tmp->right!=NULL && tmp->right!=root) tmp = tmp->right;
if(tmp->right==NULL) {
tmp->right = root;
root = root->left;
}
else {
tmp->right = NULL;
//find wrong elements
if(first==NULL && prev->val>root->val) first = prev;
if(first!=NULL && prev->val>root->val) second = root;
prev = root;
//end finding
root = root->right;
}
}
else {
//find wrong elements
if(first==NULL && prev!=NULL && prev->val>root->val) first = prev;
if(first!=NULL && prev->val>root->val) second = root;
prev = root;
//end finding
root = root->right;
}
}
//swap
int temp = first->val;
first->val = second->val;
second->val = temp;
}
};
``````

×