Recover Binary Search Tree
You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Example 1
1 3
/ -> /
3 1
\ \
2 2Input
root = [1,3,null,null,2]Output
[3,1,null,null,2]The values 1 and 3 were swapped, and swapping them back restores the binary search tree ordering.
Example 2
3 2
/ \ -> / \
1 4 1 4
/ /
2 3Input
root = [3,1,4,null,null,2]Output
[2,1,4,null,null,3]The values 2 and 3 were swapped, and correcting them restores the valid inorder order of the tree.
Constraints
- The number of nodes in the tree is in the range [2, 1000].
- -2^31 <= Node.val <= 2^31 - 1