Why it works
- The depth of a tree is its root plus the depth of its deeper subtree, and each subtree is a smaller tree of the same kind, so one call per node answers it.
- A node returns only after both of its sides have answered, so the first leaf found, 4, never decides alone: the root compares 1 with 3.
- An empty child returns 0, which makes a leaf 1 + max(0, 0) = 1 with no special case.
Complexity
Time O(n): one call per node, plus one per empty child. Memory O(h), where h is the height of the tree: the call stack holds one path from the root.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗