Maximum Depth of Binary Tree
Maximum Depth of Binary Tree is an easy Trees problem from the Blind 75. The key pattern is tree recursion or bfs, and a good solution runs in O(n) time.
Problem
Return the number of nodes on the longest root-to-leaf path in a level-order binary tree.
Examples
Example 1
Input
[5,3,9,null,4]Output
3Example 2
Input
[4,8,12,null,null,10,16]Output
3Example 3
Input
[1,null,2]Output
2Approach
A node's depth is one plus the larger depth of its two subtrees; counting levels breadth-first gives the same answer.
| Pattern | Tree recursion or BFS |
|---|---|
| Time | O(n) |
| Space | O(h) |
Watch out for
Depth counts nodes, so a single node has depth 1 and an empty tree 0.