514. Two Keys Swapped
A tournament ladder stores distinct player ratings in a binary search tree. A clerical slip exchanged the ratings of exactly two players, so the tree no longer respects the search order, although its shape is unchanged.
Repair root in place by exchanging the keys of the two misplaced nodes. Do not change the structure of the tree and do not return anything; the tree is inspected after the call. The two swapped nodes may be anywhere, including adjacent in sorted order, and the tree always has at least two nodes.
Example 1
- Input:
- root = [6,7,9,1,4,3,10]
- Output:
- [6,3,9,1,4,7,10]
- Explanation:
Keys 7 and 3 were swapped; exchanging them back restores [6,3,9,1,4,7,10].
Example 2
- Input:
- root = [2,4,6]
- Output:
- [4,2,6]
- Explanation:
The in-order sequence is 4, 2, 6, so swapping the root key 2 with its left child 4 restores [4,2,6].
Constraints
2 ≤ number of nodes ≤ 104
-104 ≤ node key ≤ 104
All keys are distinct. Exactly two keys of an otherwise valid search tree were swapped.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Graded
- Your answer is read from
rootafter your method returns. - Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)