Maximum Depth of Binary Tree（二叉树的最大深度）

题目 / Problem

中文： 给定一棵二叉树的根节点 root，返回它的最大深度。

二叉树的最大深度是从根节点到最远叶子节点的最长路径所包含的节点数。

English: Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

示例 / Examples

Example 1

Input:  root = [3,9,20,null,null,15,7]
Output: 3

        3          第 1 层 / Level 1
       / \
      9  20        第 2 层 / Level 2
         / \
        15  7      第 3 层 / Level 3

从根节点到最远叶子节点的路径包含 3 个节点，例如 3 → 20 → 15，因此最大深度为 3。
The path from the root to a farthest leaf contains 3 nodes, such as 3 → 20 → 15, so the maximum depth is 3.

Example 2

Input:  root = [1,null,2]
Output: 2

    1       第 1 层 / Level 1
     \
      2     第 2 层 / Level 2

最长根到叶路径为 1 → 2，包含 2 个节点，因此返回 2。
The longest root-to-leaf path is 1 → 2, which contains 2 nodes, so return 2.

约束 / Constraints

• 树中的节点数在 [0, 10⁴] 范围内。
  The number of nodes in the tree is in the range [0, 10⁴].
• -100 <= Node.val <= 100

解题思路一：递归深度优先搜索 / Approach 1: Recursive DFS

一棵非空二叉树的最大深度等于左右子树最大深度中的较大值再加 1：
The maximum depth of a non-empty binary tree is one plus the greater maximum depth of its two subtrees:

depth(node) = max(depth(node.left), depth(node.right)) + 1

其中额外的 1 代表当前节点。空树不包含任何节点，因此深度为 0。
The additional 1 represents the current node. An empty tree contains no nodes, so its depth is 0.

递归过程：
Recursive process:

1. 如果当前节点为 null，返回 0。
   If the current node is null, return 0.
2. 递归计算左子树的最大深度。
   Recursively calculate the maximum depth of the left subtree.
3. 递归计算右子树的最大深度。
   Recursively calculate the maximum depth of the right subtree.
4. 返回两者较大值加 1。
   Return the greater value plus 1.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *   this.val = val ?? 0;
 *   this.left = left ?? null;
 *   this.right = right ?? null;
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
function maxDepth(root) {
  if (root === null) {
    return 0;
  }

  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);

  return Math.max(leftDepth, rightDepth) + 1;
}

也可以简写为：
It can also be written more concisely:

function maxDepthConcise(root) {
  return root === null
    ? 0
    : Math.max(maxDepthConcise(root.left), maxDepthConcise(root.right)) + 1;
}

执行过程 / Walkthrough

以 root = [3,9,20,null,null,15,7] 为例，递归从叶子节点向上返回深度：
For root = [3,9,20,null,null,15,7], recursion returns depths upward from the leaves:

根节点 3 的左子树深度为 1，右子树深度为 2，所以整棵树的最大深度是 max(1, 2) + 1 = 3。
Root node 3 has a left depth of 1 and a right depth of 2, so the tree's maximum depth is max(1, 2) + 1 = 3.

DFS 复杂度 / DFS Complexity

设树中有 n 个节点，树高为 h。
Let the tree contain n nodes and have height h.

• 时间复杂度：O(n)，每个节点只访问一次。
  Time: O(n), because every node is visited once.
• 空间复杂度：O(h)，递归调用栈的深度等于树高。
  Space: O(h), because the recursion stack depth equals the tree height.
  • 平衡二叉树中为 O(log n)。
    It is O(log n) for a balanced binary tree.
  • 树退化为链表时，最坏为 O(n)。
    It is O(n) in the worst case for a skewed tree.

解题思路二：广度优先搜索 / Approach 2: Breadth-First Search

最大深度也等于二叉树的层数。可以使用队列逐层遍历，每处理完整的一层，就将深度加 1。
The maximum depth also equals the number of tree levels. Use a queue for level-order traversal and increment the depth after processing each complete level.

在每轮循环开始时保存 levelSize，它表示当前层的节点数。只处理这 levelSize 个节点，并把它们的子节点加入队列，供下一轮处理。
At the start of each iteration, save levelSize, the number of nodes in the current level. Process exactly those nodes and enqueue their children for the next iteration.

JavaScript 实现 / JavaScript Implementation

function maxDepthBFS(root) {
  if (root === null) {
    return 0;
  }

  const queue = [root];
  let front = 0;
  let depth = 0;

  while (front < queue.length) {
    const levelSize = queue.length - front;

    for (let i = 0; i < levelSize; i++) {
      const node = queue[front++];

      if (node.left !== null) {
        queue.push(node.left);
      }

      if (node.right !== null) {
        queue.push(node.right);
      }
    }

    depth++;
  }

  return depth;
}

这里使用索引 front 读取队列，避免调用 JavaScript 数组的 shift()。shift() 每次都可能移动剩余元素，带来额外开销。
An index named front reads from the queue instead of using JavaScript's shift(), which may move all remaining elements on every call.

BFS 执行过程 / BFS Walkthrough

对于 Example 1：
For Example 1:

队列处理完毕时共遍历了 3 层，因此返回 3。
When the queue is exhausted, 3 levels have been processed, so return 3.

BFS 复杂度 / BFS Complexity

• 时间复杂度：O(n)，每个节点入队和出队各一次。
  Time: O(n), because every node is enqueued and dequeued once.
• 空间复杂度：O(w)，其中 w 是二叉树的最大宽度；最坏情况下为 O(n)。
  Space: O(w), where w is the tree's maximum width; this is O(n) in the worst case.

DFS 与 BFS 对比 / DFS vs. BFS

节点数最多为 10⁴。如果树极度倾斜，递归 DFS 可能在部分 JavaScript 环境中造成调用栈溢出，此时 BFS 更稳妥。
With up to 10⁴ nodes, a highly skewed tree may overflow the recursion stack in some JavaScript environments, making BFS safer in that situation.

易错点 / Common Pitfalls

• 最大深度按路径中的节点数计算，不是边数。
  Maximum depth is measured in nodes along the path, not edges.
• 空树的最大深度为 0，单节点树的最大深度为 1。
  An empty tree has depth 0, while a single-node tree has depth 1.
• 需要取左右子树深度的最大值，而不是相加。
  Take the maximum of the two subtree depths; do not add them.
• 递归返回值必须包含当前节点，因此需要加 1。
  The recursive result must include the current node, so add 1.
• BFS 必须在处理当前层之前固定 levelSize，否则新加入的子节点可能被错误地算入同一层。
  In BFS, capture levelSize before processing a level, or newly enqueued children may be incorrectly processed in the same level.