c++ - 一棵树的直径

我正在对访问的网站进行样本测试。它带有3个问题，这些问题是公开可用的。因此，我认为讨论这些问题没有什么害处。

我的问题是

问题2/3(树的直径)
一棵树的直径是树中两片叶子之间最长路径上的节点数。下图显示了一棵直径为9的树，形成最长路径末端的叶子被阴影化(请注意，每棵长度为9的树中有多个路径，但路径长度不超过9个节点)。

特别要注意，树的直径T是以下数量中最大的:

T的左子树的直径

T的右子树的直径

穿过T

根的叶子之间的最长路径

给定树的根节点，返回树的直径

示例测试用例:

输入＃00:考虑树:

输出＃00:
5

解释:
树的直径是5

我在C++中的回答是:

int traverse(node* r) {
    if (r == NULL) { return 0;}
    return max(traverse(r->left),traverse(r->right))+1;
}
int diameterOfTree(node * r) {
    return traverse(r->left)+traverse(r->right)+1;
}

有14个测试用例，但是其中2个是错误的答案。我找不到我想念的情况。我真的不认为这是基本情况，那么我想念的是什么？

最佳答案

您可能有一棵树的直径没有穿过它的根。想象这棵树:

             / E - F - G - H - I
A - B - C - D
             \ J - K - L - M

(对于难看的ASCII艺术感到抱歉)。这里的直径是I-H-G-F-E-D-J-K-L-M。

关于c++ - 一棵树的直径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20267062/