跳到主要内容

二叉树的最大深度

问题​

给定一个二叉树 root，返回其最大深度。二叉树的最大深度是从根节点到最远叶子节点的最长路径上的节点数。

示例：

输入：root = [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7

输出：3

来源：LeetCode 104. 二叉树的最大深度

答案​

方法一：递归（DFS，推荐）​

核心思路：树的最大深度 = max(左子树深度, 右子树深度) + 1。

maxDepthRecursive.ts
function maxDepth(root: TreeNode | null): number {
  if (root === null) return 0;

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

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

一行写法：

const maxDepth = (root: TreeNode | null): number =>
  root === null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
复杂度分析
  • 时间复杂度：O(n)O(n) — 每个节点访问一次
  • 空间复杂度：O(h)O(h) — 递归栈深度为树高 h，最坏 O(n)O(n)（链状树），最优 O(log⁡n)O(\log n)（平衡树）

方法二：BFS 层序遍历​

核心思路：层序遍历，数有多少层就是最大深度。

maxDepthBFS.ts
function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;

  const queue: TreeNode[] = [root];
  let depth = 0;

  while (queue.length > 0) {
    const levelSize = queue.length;
    depth++;

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }

  return depth;
}
何时选 BFS？

当树极度不平衡（类似链表）时，BFS 的空间优于 DFS。因为 BFS 的空间是最宽层的宽度，DFS 的空间是树的高度。

方法三：迭代 DFS（显式栈）​

maxDepthIterative.ts
function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;

  const stack: Array<{ node: TreeNode; depth: number }> = [
    { node: root, depth: 1 },
  ];
  let max = 0;

  while (stack.length > 0) {
    const { node, depth } = stack.pop()!;
    max = Math.max(max, depth);

    if (node.right) stack.push({ node: node.right, depth: depth + 1 });
    if (node.left) stack.push({ node: node.left, depth: depth + 1 });
  }

  return max;
}

常见面试追问​

Q1: 最小深度怎么求？(LeetCode 111)​

答案：最小深度是到最近叶子节点的距离，注意叶子节点的定义（左右子节点都为 null）：

function minDepth(root: TreeNode | null): number {
  if (!root) return 0;
  if (!root.left) return minDepth(root.right) + 1;
  if (!root.right) return minDepth(root.left) + 1;
  return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
注意陷阱

不能简单写 Math.min(left, right) + 1，因为如果一边为 null（深度 0），应该走另一边。例如只有右子树的情况，最小深度不是 1（根节点不是叶子）。

Q2: 如何判断是否是平衡二叉树？(LeetCode 110)​

答案：

function isBalanced(root: TreeNode | null): boolean {
  function height(node: TreeNode | null): number {
    if (!node) return 0;

    const left = height(node.left);
    if (left === -1) return -1; // 提前剪枝

    const right = height(node.right);
    if (right === -1) return -1;

    if (Math.abs(left - right) > 1) return -1; // 不平衡
    return Math.max(left, right) + 1;
  }

  return height(root) !== -1;
}

Q3: 如何计算各节点的深度？​

答案：

function nodeDepths(root: TreeNode | null): Map<TreeNode, number> {
  const depths = new Map<TreeNode, number>();

  function dfs(node: TreeNode | null, depth: number): void {
    if (!node) return;
    depths.set(node, depth);
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  }

  dfs(root, 1);
  return depths;
}

相关链接​