计算的不是树的直径,而是最远的两个叶子节点!!!
如果你直接计算树的直径,那么如果这棵树只有一个叶子节点,算出来的直径就是根节点到最远的叶子结点的距离(这是不正确的)
解决方案:
1.在进行dfs时进行特判如果该节点的度为1,且不为根节点,也就是不为1号节点,这时才更新最长路。
2.假如我们使用maxx变量来记录树的高度减去最远的两个叶子节点的距离,那么它是可以为负数的,因此开始时要将其设为极小值!!!
为了更直观一些,下面给出一组hack数据:
Input:
2
4 1 2 3
4 1 2 3
4 4
Output:
4