手帐 Blog

主题

复盘 · LC 104 二叉树的最大深度 ​

题目 ​

题意 ​

根到最远叶子的节点数（含根）即为最大深度；空树深度为 0。

边界：空树、单节点、偏斜成链、左右高度差很大。

涉及算法 ​

标签一句话
DFS / 递归depth = 1 + max(左深度, 右深度)
BFS 层序一层一层数到最后一层

教程对照：17 · 二叉树递归经典（深度、对称、路径和、直径）。

评价我的解法 ​

我的代码（摘自 104-二叉树的最大深度/index.js）：

javascript
function deep(root, val) {
  if (!root) {
    return 0;
  }
  const leftValue = deep(root.left);
  const rightValue = deep(root.right);
  return Math.max(leftValue, rightValue) + 1;
}

var maxDepth = function (root) {
  const res = deep(root, 1);
  return res;
};

核心对：空返回 0，非空取左右较大再 +1——就是定义本身。

  • 时间 O(n)，空间 O(h)。
  • 糙点：val 参数声明了却从未使用，调用还传了 1；maxDepth 只是薄包装，可直接写成递归主体，少一层噪音。
  • 和 94 一样，说明二叉树递归已经上手；下一步是把「对称 / 直径」等同家族题也压成一句定义。

最佳题解 ​

精简递归（与标准题解同构）：

javascript
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (!root) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};
  • 时间 O(n)，空间 O(h)。
  • 为何更优：无多余参数与包装，面试板书更干净。

BFS 备选（按层计数）：

javascript
var maxDepth = function (root) {
  if (!root) return 0;
  const queue = [root];
  let depth = 0;
  while (queue.length) {
    let size = queue.length;
    while (size--) {
      const node = queue.shift();
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    depth++;
  }
  return depth;
};

关联题目 ​

题为何相关
111. 二叉树的最小深度对称题；注意「叶子」定义
543. 二叉树的直径深度递归里顺带求左右和
110. 平衡二叉树深度 + 左右差 ≤ 1

一句话带走 ​

最大深度：空为 0，否则 1 + max(左, 右)——定义即代码。