Description
Two nodes of a binary search tree are swapped by mistake. Recover the tree without changing its structure. Find and swap the two incorrect nodes.
Examples
Input:
root = [1,3,null,null,2]Output:
[3,1,null,null,2]Explanation:
3 and 1 are swapped. Fix the BST.
Input:
root = [2,1,4,null,null,3,6]Output:
[2,1,4,null,null,6,3]Explanation:
In this BST, nodes 3 and 6 are swapped. The correct BST should have 6 as the right child of 4 and 3 as the left child of 4. After swapping these values back, the in-order traversal becomes [1,2,3,4,6] which is sorted.
Input:
root = [5,3,8,2,4,7,10,null,null,null,null,6,null,9]Output:
[5,3,8,2,4,6,10,null,null,null,null,7,null,9]Explanation:
Here nodes 6 and 7 are swapped. Node 6 should be the left child of 7's original parent (node 8), and node 7 should be the left child of 8. This demonstrates swapping between nodes that are not directly parent-child related but are in different subtrees.
Constraints
- •
2 ≤ number of nodes ≤ 1000 - •
-2³¹ ≤ Node.val ≤ 2³¹ - 1