Given the root node of a binary search tree (BST), where exactly two nodes have had their values swapped, restore the BST by swapping the values of these two nodes so that the BST property is satisfied. The structure of the tree must remain unchanged. The input and output are represented as level-order lists, where None denotes a missing child.
Example 1
Input: [5,2,7,1,4,None,6]
Output: [5,2,7,1,4,None,6]
Explanation: No swap needed; already a valid BST.
Example 2
Input: [8,3,10,1,6,None,14,None,None,4,7,13,None]
Output: [8,3,10,1,6,None,14,None,None,4,7,13,None]
Explanation: Already a valid BST.
Example 3
Input: [9,5,12,2,7,11,15,None,None,6,8]
Output: [9,5,12,2,7,11,15,None,None,6,8]
Explanation: Already a valid BST.
Example 4
Input: [6,3,8,1,7,None,10]
Output: [6,3,8,1,7,None,10]
Explanation: Already a valid BST.
Example 5
Input: [4,2,6,1,3,5,7]
Output: [4,2,6,1,3,5,7]
Explanation: Already a valid BST.
Constraints
Case 1
Input: [7,2,9,1,5,None,10,None,None,4,6]
Expected: [7,2,9,1,5,None,10,None,None,4,6]
Case 2
Input: [10,5,15,2,7,12,20,None,None,6,8]
Expected: [10,5,15,2,7,12,20,None,None,6,8]
Case 3
Input: [12,6,14,3,8,None,15,None,None,7,9]
Expected: [12,6,14,3,8,None,15,None,None,7,9]
Case 4
Input: [5,3,8,2,4,7,9]
Expected: [5,3,8,2,4,7,9]
Case 5
Input: [13,7,18,3,9,15,20,None,None,8,10]
Expected: [13,7,18,3,9,15,20,None,None,8,10]