手帐 Blog

主题

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

题目 ​

题意 ​

给定一棵二叉树根节点，返回其最大深度——从根到最远叶子的节点数。

  • 空树深度为 0。
  • 单节点深度为 1。

涉及算法 ​

标签一句话
DFS / 递归depth(node) = 1 + max(depth(left), depth(right))
BFS层序数层数，也能做

教程对照：17 · 二叉树递归经典。

评价我的解法 ​

二刷已经收敛成标准定义，没有一刷里多余的参数或辅助函数包装。

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

javascript
var maxDepth = function (root) {
  if (!root) {
    return 0;
  }
  return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
};

评价：

  1. 定义正确：空返回 0，有节点则左右深度取 max 再 +1，和教科书一致。
  2. 可写得更对称：1 + Math.max(maxDepth(root.left), maxDepth(root.right)) 语义更清晰（「本层 1 + 子树深度」），当前写法等价，无功能问题。
  3. 复杂度：时间 O(n)，空间 O(h) 递归栈——本题标准。

小结：二刷过关；这一定义会直接喂给今天的 543（直径）和 226（翻转时的成对递归手感）。

最佳题解 ​

与你写法等价的常见写法：

javascript
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
  • 时间 O(n)，空间 O(h)。
  • BFS 备选：队列层序，每层 size 循环一次，层数 +1。

关联题目 ​

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

一句话带走 ​

最大深度：空 0，否则 1 + max(左, 右)——默写稳了再去做直径。