💬 Discord
Sign In
NeetCode #387LC-104EasyTreesBlind 75NC 150NC 250
← Back to All Problems

#387 · #104 · Maximum Depth of Binary Tree(二叉树的最大深度)

📌 Problem Statement & Constraints

Given the root of a binary tree, return its maximum depth: the number of nodes along the longest path from the root down to the farthest leaf. Constraints: the number of nodes is in [0, 10^4].

💡 Core Algorithmic Approaches

  1. The depth of a tree is 1 + max(depth(left), depth(right)), with an empty tree having depth 0.
  2. That recurrence is a direct recursion.
  3. An iterative BFS counting the number of levels is an equivalent alternative and avoids recursion depth concerns.
  4. This is the template for all height-based tree problems.

💻 Benchmark Python3 Implementation

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))


# Iterative BFS: count the levels
class Solution2:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        from collections import deque
        if not root:
            return 0
        depth = 0
        q = deque([root])
        while q:
            depth += 1
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return depth

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): every node is visited once.
💾 Space Complexity
O(h) for the recursion stack; O(w) for the BFS queue, where w is the maximum width.

⚠️ Interview Pitfalls & Follow-ups

  • Returning 0 for a single-node tree: the depth of a leaf is 1, so the base case must only trigger for None.
  • Counting edges instead of nodes: the problem asks for the number of nodes on the longest path, so a leaf has depth 1.
  • Using max(depth(left), depth(right)) without the +1: the current node would not be counted.
  • Deep recursion: with 10^4 nodes the recursion limit can be reached for a degenerate tree; the BFS variant avoids that.