A parts catalogue is a binary search tree with distinct numbers. During maintenance a technician unhooked two whole branches (two subtrees, neither inside the other), and hung each one where the other had been: the node that was the root of the first branch is now a child of the second branch's old parent, on the same side, and vice versa. Nothing inside either branch changed.
Given the damaged tree, hang the two branches back and return the root of the repaired search tree. Exactly one such exchange happened, so the repaired tree is unique.
Examples
50 50
/ \ / \
30 40 30 70
/ \ / \ ==> / \ / \
20 70 35 45 20 40 60 80
/ \ / \
60 80 35 45
Input: root = build_tree([50, 30, 40, 20, 70, 35, 45, None, None, 60, 80])
Output: tree_to_list(...) == [50, 30, 70, 20, 40, 60, 80, None, None, 35, 45]
Input: root = build_tree([5, 8, 2, 7, 9, 1, 3])
Output: [5, 2, 8, 1, 3, 7, 9]
Constraints
3 <= number of nodes <= 2 * 10**4; the tree may be very deep- Trying every pair of branches is far too slow for the largest tests.
Goals
- See that swapping two subtrees exchanges two contiguous blocks of the inorder sequence
- Recover both block lengths by comparing with the sorted order
- Find the two branch roots from inorder positions and sizes, then relink them