Why it works
- Two sides mirror each other exactly when their roots are equal, the left side's left child mirrors the right side's right child, and the left side's right child mirrors the right side's left child.
- So the pairs cross: 5 on the far left meets 5 on the far right, the outer pair, and 7 meets 9 by the middle, the inner pair. A node is never compared with the one in the same place under the other 6.
- The first pair that differs returns false straight up, so the rest is never compared.
Complexity
Time O(n): each node is in at most one pair, and each pair is compared once. Memory O(h), where h is the height of the tree: the call stack holds one path of pairs.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗