Medium

Quiz

#99 Recover Binary Search Tree

APPROACH

In the BST rooted at root, exactly two nodes had their values accidentally swapped. Restore the tree by swapping those values back without altering the tree's structure.

Example 1:

Input: root = [1,3,null,null,2]

Output: [3,1,null,null,2]

Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

Input: root = [3,1,4,null,null,2]

Output: [2,1,4,null,null,3]

Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

1 of 4

1:00

What is the optimal approach for this problem?