Restore a Search Tree After Two Values Were Swapped
Implement fixSwappedNodes
You are given the root of a binary tree that was a valid binary search tree with distinct values, until the values of exactly two of its nodes were swapped with each other. Restore the tree by putting the two values back where they belong, without changing the shape of the tree, and return its root.
The inorder sequence of a search tree is sorted, so a swap leaves the sequence sorted except for two exchanged values. Comparing with a sorted copy finds them; a single inorder walk that watches for a value smaller than its predecessor finds them without any extra storage.
Example 1:
Input: root = [50,30,20,70,40,60,80]
Output: [50,30,70,20,40,60,80]
Example 2:
Input: root = [10,20,30]
Output: [20,10,30]
Example 3:
Input: root = [40,20,60,10,50,30,70]
Output: [40,20,60,10,30,50,70]
+ 13 hidden test cases run on Submit.
Constraints:
- ●
2 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ●
The tree WAS a binary search tree, but the values of exactly two of its nodes have been swapped with each other; the shape is unchanged. It is given by its root node - ●
Restore the search-tree property by putting the two values back where they belong — change only the values of those two nodes, not the shape - ●
Return the root of the repaired tree (checked as a level-order list)
root =