#104
Maximum Depth of Binary Tree
Easy Recursive height
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the number of nodes on the longest path from the root down to a leaf.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the number of levels.
Why this works: depth = 1 + deeper of the two subtrees; an empty tree is 0.
Example: 3 (9, 20 (15, 7))
depth(9) = 1, depth(20) = 2depth(3) = 1 + 2 = 3
✦Hints open one at a time
The depth of a tree is 1 + the larger depth of its two subtrees.
An empty tree has depth 0.
↗Approach
Postorder recursion: compute both children's depths, return 1 + max.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}!Common mistake
Returning 1 for a null node, which adds one level to everything.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon