树的直径计算：为何需保留递归调用diameter函数的技术疑问

你的疑问非常合理——如果只看简单的树结构，确实容易误以为直径一定经过根节点，但实际上树的最长路径（直径）完全可能存在于某个子树内部，这时候你的简化代码就会出错。

先回顾一下两段代码：

原代码：

def diameter(root):
    if root is None:
        return 0
    lheight = height(root.left)
    rheight = height(root.right)
    ldiameter = diameter(root.left)
    rdiameter = diameter(root.right)
    return max(lheight + rheight + 1, max(ldiameter, rdiameter))

你的简化代码：

def diameter(root):
    if root is None:
        return 0
    lheight = height(root.left)
    rheight = height(root.right)
    return lheight + rheight + 1

反例：直径存在于子树内部的情况 #

我们构造这样一棵二叉树：

root
       /
      A
     / \
    B   C
   /     \
  D       E
 /         \
F           G

这棵树的真正直径是路径 F → D → B → A → C → E → G，包含7个节点。

现在看两段代码的计算结果：

1. 你的简化代码：

   • height(root.left) 是height(A)，计算得4（从A到F或G的高度都是3，加1后是4）
   • height(root.right) 是0（root没有右子树）
   • 返回结果是 4 + 0 +1 =5，显然和真实直径7不符。

2. 原代码：

   • 递归计算diameter(A)时，height(B)是3，height(C)是3，所以3+3+1=7
   • 同时递归计算diameter(B)和diameter(C)，它们的结果都小于7
   • 所以diameter(A)返回7
   • 原代码最终取max(5,7)，得到正确结果7

原代码的逻辑为什么正确？ #

原代码其实考虑了三种可能的最长路径：

• 路径经过当前节点：由左子树高度+右子树高度+当前节点（即lheight + rheight +1）
• 路径完全在左子树内部：递归计算左子树的直径（ldiameter）
• 路径完全在右子树内部：递归计算右子树的直径（rdiameter）

最终取这三者的最大值，才能覆盖所有可能的最长路径场景。而你的简化代码只考虑了第一种情况，漏掉了路径完全藏在子树里的情况，所以会在类似上述的场景下出错。

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