Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0.
Example 1
Input: root = [3,9,20,null,null,15,7]
Output: 3
The path 3, 20, 15 has three nodes.
Example 2
Input: root = [1,null,2]
Output: 2
Constraints
- The number of nodes is in the range 0 to 10^4
- -100 <= Node.val <= 100
Hints
Frequently asked at: Amazon, LinkedIn, Apple, TCS
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
You could list every root to leaf path and measure each one, but that repeats work. A tree is defined recursively, so its depth is too: a node adds one level on top of the deeper of its two subtrees. Each node is visited once, giving O(n). The same answer also comes from BFS by counting how many levels the queue processes.
Algorithm
- If
rootis null, return 0. - Recursively compute
left = maxDepth(root.left)andright = maxDepth(root.right). - Return
1 + max(left, right).
Time:
O(n)Space: O(h) recursion depthInterview tip: On a very skewed tree with 10^4 nodes, recursion depth equals the number of nodes. Mention that BFS (level counting) avoids deep recursion if the interviewer worries about stack overflow.
class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))Ctrl + Enter runs the examples