Why it works
- In a complete tree the last level fills from the left. If the leftmost and the rightmost paths are the same length, that level is full too, and a perfect tree of h levels has 2^h − 1 nodes.
- If they differ, at least one of the two subtrees is perfect, so one of the two calls answers at once from its edges. Only one path down is ever counted the long way.
Complexity
Time O(log² n): the long way goes down one path of O(log n) calls, and each call walks two edges of O(log n) nodes. Memory O(log n) for the call stack.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗