树的直径

Question

我有一个代码可以计算树的直径。根据我的理解，直径是 2 个叶节点之间最长路径中的节点数。

密码是：

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))

其中height是计算节点高度的函数。但是，我觉得没有必要对 diameter 函数进行递归调用，如下面的代码片段所示，因为它提供相同的输出。

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

    return lheight + rheight + 1

为什么第一个代码中需要递归调用 diameter？

可能我找不到lheight + rheight + 1小于max(ldiameter, rdiameter)的情况。

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

Answer 1

需要递归调用 diameter 函数，因为树的直径不一定通过树的根。

您的第二段代码仅给出结果 height(left subtree of root) + height(right subtree of root) + 1 如果直径“路径”通过根（但并非总是），这将是正确答案。

这种树的一个例子是 -

中的第二棵树

在上面的第二张图片中，如果我们应用你的第二个代码，我们将得到结果 7 但正确答案是 9（如果我们考虑直径不通过根)

树的直径

Diameter of the tree

python

tree

recursive-datastructures