You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
We know that inorder traversal of BST is sorted, so we can use this fact to find the two nodes swapped.(In question it's confirmed that only two nodes are swapped)
TC: O(n)
Code
classSolution {
public:
TreeNode *firstNode, *secondNode, *prevNode;
voidrecoverTree(TreeNode* root)
{
inorder(root);
// swap the values of misplaced nodesswap(firstNode->val, secondNode->val);
}
voidinorder(TreeNode* root)
{
if (root == NULL) return;
inorder(root->left);
if (prevNode!=NULL && root->val < prevNode->val) {
// set first nodeif (firstNode == NULL) firstNode = prevNode;
// set/update second node
secondNode = root;
}
// update previous node
prevNode = root;
inorder(root->right);
}
};