99 recovery binary serach tree

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;
}