一棵树的直径

Question

我正在做 interviewstreet.com 的样本测试。它包括三道题目，这些题目是公开可见的。所以我认为没有讨论这些问题的危害。

我的问题是：

问题 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个用例的答案是错误的。我找不到哪些用例是我缺少的。我不认为这是基本情况，那么我缺少什么？

- Sarp Kaya

Answer 1

您可能会发现树的直径并不经过其根部。想象一棵这样的树：

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

（对于丑陋的ASCII艺术表示感到抱歉）。 这里的直径为I-H-G-F-E-D-J-K-L-M。

- Ivaylo Strandjev

---

初始调用是 diameterOfTree(root);，所以我不认为那是问题所在。 - Sarp Kaya

你没有理解我的意思。有些情况下，直径并不经过根部。请看我的例子。 - Ivaylo Strandjev

抱歉，刚看到更新。现在我明白你的意思了。 - Sarp Kaya

在这种情况下，直径是多少？13 还是 10？ - Sarp Kaya

根据此文献：“一棵树的直径是从树叶中最长路径上的节点数。” 因此，答案是10。 - artur grzesiak

@PhamTrung 我没有提供任何代码，我只是画了一棵树，作为所提出解决方案的反例。我知道如何找到一棵树的直径，但这不是问题的一部分。 - Ivaylo Strandjev