我正在对访问的网站进行样本测试。它带有3个问题,这些问题是公开可用的。因此,我认为讨论这些问题没有什么害处。
我的问题是
问题2/3(树的直径)
一棵树的直径是树中两片叶子之间最长路径上的节点数。下图显示了一棵直径为9的树,形成最长路径末端的叶子被阴影化(请注意,每棵长度为9的树中有多个路径,但路径长度不超过9个节点)。
特别要注意,树的直径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/