Blind 75 · Trees
Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0.
Example 1: Input: root = [3,9,20,null,null,15,7] Output: 3 Example 2: Input: root = [1,null,2] Output: 2 Example 3: Input: root = [] Output: 0 Example 4: Input: root = [1] Output: 1
0 <= number of nodes <= 10^4 -100 <= Node.val <= 100
Binary trees, and recursion over them: solve the children, combine, return. The base case is almost always the empty tree.
Depth-first order (pre, in, post) and breadth-first by level — and knowing which one a problem is really asking for.
A tree's depth is one more than its deepest subtree, and an empty tree has none. That sentence is the whole solution — the value here is checking that recursion over trees feels natural, because everything else in this section assumes it does.
1. Empty tree: 0.
2. Otherwise: 1 plus the larger of the two subtree depths.
Time O(n). Space O(h) for the stack; a level-order walk trades it for a queue of the widest level.