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:
Swapping the misplaced values back restores the BST, giving [3,1,null,null,2].
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:
Swapping the misplaced values back restores the BST, giving [5,3,8,2,4,6,10,null,null,null,null,7,null,9].
Constraints
- •
2 ≤ number of nodes ≤ 1000 - •
-2³¹ ≤ Node.val ≤ 2³¹ - 1