我正在对访问的网站进行样本测试。它带有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/

    10-12 20:02