The root of a binary search tree (BST) is given. In a BST, every value in the left part of a node is smaller than the node, and every value in the right part is bigger. In this tree exactly two nodes had their values swapped by mistake. Fix the tree by swapping the two values back. Do not change the shape of the tree.
Return the fixed tree in the same array form.
How the judge passes the data
Examples
Example 1:
Input: root = [5,2,8,1,6,7,9]
Output: [6,2,8,1,5,7,9]
Explanation: In-order the tree reads 1, 2, 6, 5, 7, 8, 9. The values 5 and 6 are out of place. Swap them.
Example 2:
Input: root = [4,2,3]
Output: [3,2,4]
Explanation: The left child 2 is fine, but the right child 3 is smaller than the root 4. Swap 4 and 3.
Example 3:
Input: root = [2,null,1]
Output: [1,null,2]
Explanation: The right child 1 is smaller than the root 2. Swap them.