Maximum depth
The depth of a tree is 1 plus the maximum depth of its two subtrees. About 8 minutes.
What is tree depth?
How many floors does a building have? You count from the ground up to the top floor. The depth of a binary tree (also called its height) is the same idea: the number of nodes along the longest path from the root down to the farthest leaf.
An empty tree has depth 0, and a single node has depth 1, because the path is just that one node.
How deep is the tree under 3? Ask each side, take the deeper one, add 1 for this level.
Picking the deeper branch
Say the left branch is 3 levels deep and the right branch is only 1. The deepest leaf must lie down the left side, so that is the one that counts. Add 1 for the current node on top, and the total depth is 1 + 3 = 4.
So each node asks its two sides how deep they go, takes the larger answer, and adds 1 for itself.
if not root:
return 0
left = max_depth(root.left)
right = max_depth(root.right)
return 1 + max(left, right)A root node has a left child with depth 4 and a right child with depth 2. What is the max depth?
- A5
- B6
- C4
Show the answer
5. 1 + max(4, 2) = 1 + 4 = 5.
Maximum depth
Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. If the tree is empty, return 0.
root = [3, 9, 20, null, null, 15, 7] → 3
0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val ≤ 1,000,000