Maximum Depth of Binary Tree
EasyThe problem
Return how many nodes are on the longest path that starts at the root and goes down to a leaf. An empty tree has depth 0.
- Example 1Input: root = [3, 9, 20, null, null, 15, 7]Output: 3
The path 3 → 20 → 15 has 3 nodes, and no path is longer.
- Example 2Input: root = [1, null, 2]Output: 2
- Example 3Input: root = []Output: 0
Limits
- 0 ≤ number of nodes ≤ 10,000
- -100 ≤ node value ≤ 100
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
The depth of a node is defined using the depths of its children.
The idea
1 + max(depth(left), depth(right)); an empty node has depth 0.
Target: O(n) time, O(h) space
Go function shape
func maxDepth(root *TreeNode) intReference solution
Tested with go test. Try it yourself first, then compare.
// MaxDepth: number of nodes on the longest root-to-leaf path.
func MaxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return 1 + max(MaxDepth(root.Left), MaxDepth(root.Right))
}