Someone swapped the values of exactly two nodes of a binary search tree with distinct values, so the tree is no longer ordered. Put the two values back without changing the shape of the tree (swap node values, do not move nodes) and return the root.
Examples
20 20
/ \ / \
10 30 ==> 10 30
/ \ / \ / \ / \
5 25 15 40 5 15 25 40
Input: root = build_tree([20, 10, 30, 5, 25, 15, 40])
Output: tree_to_list(...) == [20, 10, 30, 5, 15, 25, 40]
2 2
/ \ => / \
3 1 1 3
Input: root = build_tree([2, 3, 1])
Output: [2, 1, 3]
Constraints
2 <= number of nodes <= 3000- Values are distinct and exactly two of them are misplaced
- O(n) time; aim for O(h) extra space
Goals
- Detect the out-of-order positions in the inorder sequence
- Handle both adjacent and distant swaps
- Fix the tree by swapping values without changing its shape