二叉树直径求解遇阻：最长路径不经过根节点的失败案例

问题背景 #

你在解决LeetCode的「二叉树的直径」问题时，尝试了暴力递归解法，但在最长路径不经过根节点的测试用例中失败。你的代码如下：

var diameterOfBinaryTree = function(root) {

  if (root === null) return 0;
  let max_height = 0;

  function maxDepth(node) {
    if (node === null) return 0;
    var lh = maxDepth(node.left);
    var rh = maxDepth(node.right);

    return 1 + Math.max(lh, rh);
  }

  max_height = Math.max(max_height, maxDepth(root.left) + maxDepth(root.right));

  diameterOfBinaryTree(root.left);
  diameterOfBinaryTree(root.right);

  return max_height
}

错误原因 #

你的代码核心问题在于**max_height是局部变量**：

• 当递归调用diameterOfBinaryTree(root.left)或diameterOfBinaryTree(root.right)时，这些子递归函数里的max_height是各自独立的局部变量，和当前函数的max_height完全无关。
• 最终返回的max_height只计算了根节点左右子树的深度之和，完全没考虑子树内部存在更长路径的情况。比如测试用例中最长路径在某个子树里时，子递归里算出的更大值根本不会传递到当前层的max_height中。

修正后的暴力解法 #

把max_height改成可以在递归间共享的变量，比如用数组（引用类型，修改内部值会同步到所有引用）：

var diameterOfBinaryTree = function(root) {
  if (root === null) return 0;
  let maxDiameter = [0]; // 用数组实现引用传递，共享最大值

  function maxDepth(node) {
    if (node === null) return 0;
    const lh = maxDepth(node.left);
    const rh = maxDepth(node.right);
    return 1 + Math.max(lh, rh);
  }

  // 计算当前节点的直径，更新共享的最大值
  maxDiameter[0] = Math.max(maxDiameter[0], maxDepth(root.left) + maxDepth(root.right));
  
  // 递归处理左右子树，持续更新最大值
  diameterOfBinaryTree(root.left, maxDiameter);
  diameterOfBinaryTree(root.right, maxDiameter);

  return maxDiameter[0];
};

优化到O(N)的解法 #

暴力解法的时间复杂度是O(N²)，因为每个节点会重复计算左右子树深度。优化思路是在计算深度的同时直接更新直径，每个节点只遍历一次：

var diameterOfBinaryTree = function(root) {
  let maxDiameter = 0;

  function dfs(node) {
    if (!node) return 0;
    const leftDepth = dfs(node.left);
    const rightDepth = dfs(node.right);
    // 计算当前节点作为路径中点的直径，更新全局最大值
    maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
    // 返回当前节点的最大深度，供父节点计算使用
    return 1 + Math.max(leftDepth, rightDepth);
  }

  dfs(root);
  return maxDiameter;
};

这个解法里，每次递归计算节点深度时，顺便算出以该节点为中心的路径长度（左右深度之和），并更新全局的最大直径。整个过程每个节点只访问一次，时间复杂度O(N)，空间复杂度O(H)（H为树的高度，对应递归栈开销）。

内容的提问来源于stack exchange，提问作者ABGR