TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write max_depth(root) -> int: the number of nodes on the longest path from the root down to a leaf. An empty tree (None) has depth 0, and a single node has depth 1.
# 8
# / \
# 3 10
# / \
# 1 14
# /
# 13
max_depth(root) # 4 (8 -> 10 -> 14 -> 13)
max_depth(None) # 0
- Up to 1,000 nodes; values are arbitrary integers and may repeat. The Python tests stay within 400 levels, so plain recursion is safe under its default limit of 1,000 frames.
- Aim for O(n).
Show hint
How does the depth of a tree relate to the depths of its two subtrees? Start from the empty tree.