1 2 3 4 5 6
1 5 3 4 2 6
5>3 发现第一个错误节点5，prev
4>2 发现第二个错误节点2 ,curr
void inOrder(struct TreeNode * root,struct TreeNode** prev,struct TreeNode** first,struct TreeNode** second){
if(root == NULL) return;
//search left tree
inOrder(root->left, prev, first, second);
//in inorder traversal of BST, prev should always have smaller value than current value
if((*prev) != NULL && (*prev)->val >= root->val){
//incorrect smaller node is always found as prev node
if(*first == NULL)
*first = *prev;
//incorrect larger node is always found as curr(root) node
*second = root;
}
//update prev node
*prev = root;
//search right tree
inOrder(root->right, prev, first, second);
}
void recoverTree(struct TreeNode* root) {
//use inorder traversal to detect incorrect node
struct TreeNode * prev = NULL;
struct TreeNode * first = NULL;
struct TreeNode * second = NULL;
inOrder(root, &prev, &first, &second);
int temp = first->val;
first->val = second->val;
second->val = temp;
}
