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 tree satisfies BST properties. The structure of the tree must not be changed. The input and output are represented as level-order arrays, where None denotes a missing child.
Example 1
Input: [5,2,7,1,4,None,8,None,None,3,6]
Output: [5,2,7,1,3,None,8,None,None,4,6]
Explanation: Nodes with values 3 and 4 are swapped. After recovery, the tree is a valid BST.
Example 2
Input: [10,5,15,2,8,None,20,None,None,7,12]
Output: [10,5,15,2,7,None,20,None,None,8,12]
Explanation: Nodes with values 7 and 8 are swapped. After recovery, the tree is a valid BST.
Constraints
Case 1
Input: [6,3,8,1,4,7,9,None,None,None,None,None,None]
Expected: [6,3,8,1,4,7,9,None,None,None,None,None,None]
Case 2
Input: [4,2,6,1,5,None,7]
Expected: [4,2,6,1,5,None,7]
Case 3
Input: [9,5,11,2,7,None,13,None,None,6,8]
Expected: [9,5,11,2,6,None,13,None,None,7,8]
Case 4
Input: [12,8,14,3,10,None,16,None,None,9,11]
Expected: [12,8,14,3,9,None,16,None,None,10,11]