手帐 Blog

主题

复盘 · LC 543 二叉树的直径 ​

题目 ​

题意 ​

直径 = 任意两节点之间最长路径的边数（不是节点数）。

  • 路径可以不过根。
  • 单节点直径为 0。

边界：直径落在某棵子树内部、偏斜树、根左右都深但直径却在一侧更长。

涉及算法 ​

标签一句话
DFS + 全局答案对每个节点算「左深度 + 右深度」，取全局 max；递归仍返回「以该节点为根的深度」
最大深度543 = 在 104 的深度递归里多记一笔

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

评价我的解法 ​

初版（错） ​

我的代码（摘自 543-二叉树的直径/index.js）：

javascript
function findDeep(root) {
  if (!root) {
    return 0;
  }

  return Math.max(findDeep(root.left) + 1, findDeep(root.right) + 1);
}

var diameterOfBinaryTree = function (root) {
  return findDeep(root.left) + findDeep(root.right);
};

自评已点出：只算了「经过根」的左右深度和，101/106 过——直径完全可以只在左子树或右子树内部。

修正版（对） ​

我的代码（摘自 543-二叉树的直径/index2.js）：

javascript
var diameterOfBinaryTree = function (root) {
  let maxDeep = 0;
  function deep(root) {
    if (!root) {
      return 0;
    }
    const lDeep = deep(root.left);
    const rDeep = deep(root.right);
    maxDeep = Math.max(maxDeep, lDeep + rDeep);
    return Math.max(lDeep + 1, rDeep + 1);
  }
  deep(root);
  return maxDeep;
};

评价：

  1. 套路对：后序算左右深度，用 lDeep + rDeep（边数）更新全局，返回值仍是「高度」给父节点用——标准解。
  2. 命名：maxDeep 实际是直径（边数），叫 maxDiam / ans 更不易和「深度」混淆。
  3. 空树：deep(null) 不更新，maxDeep 仍 0，正确。
  4. 复杂度：时间 O(n)，空间 O(h)；比初版「只看根」信息完整得多。

小结：踩坑有价值——「路径不过根」是树题高频坑；修正后已是面试可讲版本。

最佳题解 ​

与修正版同构，仅命名更清楚：

javascript
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
  let ans = 0;
  function height(node) {
    if (!node) return 0;
    const L = height(node.left);
    const R = height(node.right);
    ans = Math.max(ans, L + R);
    return 1 + Math.max(L, R);
  }
  height(root);
  return ans;
};
  • 时间 O(n)，空间 O(h)。
  • 为何优于初版：每个节点都是潜在「路径最高点」，必须全局扫描。

关联题目 ​

题为何相关
104. 二叉树的最大深度高度定义直接复用
124. 二叉树中的最大路径和同一「全局 + 返回给父」框架，升级为权值
687. 最长同值路径直径思想 + 值相等约束

一句话带走 ​

直径：每个节点看左右高度之和，取全局 max；递归仍只返回高度——别默认路径过根。