Loading...
You are given a binary tree root that was a binary search tree until exactly two nodes had their values swapped. Swap them back and return the root of the repaired tree.
The tree's shape does not change.
You can assume all values are distinct, exactly two values were swapped, and the repaired tree is a valid binary search tree.
Your function receives root as a TreeNode and returns the root of the repaired tree the same way. The node type is provided for you, with val, left, and right fields.
The examples below write trees as their level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how trees are displayed; the encoding and decoding are done for you.
root is in the range [2,104].Node.val ≤109Node.val are unique.The in-order sequence should be sorted, but reading it out gives `3, 2, 1`: the walk drops from `3` to `2`, then from `2` to `1`. The node from the FIRST drop (`3`) and the node from the LAST drop (`1`) are the two to swap, restoring `1, 2, 3`.
The in-order sequence reads `1, 3, 2, 4`: only one drop, from `3` to `2`. Swapping those two values restores the sorted order `1, 2, 3, 4`.
The in-order sequence reads `2, 1`, a single drop. Swapping the two values restores `1, 2`.