In correct BST, inorder traversal is strictly increasing. After swap, there are violations.
Case 1: Adjacent swap (e.g., swap positions 3 and 4 in sorted order)
- One violation:
prev > currentat one point - Swap
prevandcurrent
Case 2: Non-adjacent swap (e.g., swap positions 1 and 5)
- Two violations
- First violation:
first = prev - Second violation:
second = current - Swap
firstandsecond
def recoverTree(root):
first = second = prev = null
def inorder(node):
nonlocal first, second, prev
if not node: return
inorder(node.left)
if prev and prev.val > node.val:
if not first:
first = prev
second = node
prev = node
inorder(node.right)
inorder(root)
first.val, second.val = second.val, first.val