当计算树的直径为什么单独计算高度是不够的

Question

在发现树的直径，我们考虑的最大如下：

1：左子树的直径

2：直径右子树

3：左子树+右子树的高度的高度+ 1

为什么这三个是必要的？为什么只有3个人是不够的。让我们看一个简单的例如3节点树和2节点树。在前3点单独给予1 + 1 + 1 = 3 而在后一种情况下3点独自给出0 + 1 + 1 = 2

在这种情况下，为什么我们需要找到三个最大。 PLZ解释

Answer 1

考虑下面的树：

  [A] 
     /
     [B] 
    / \ 
    [C]  [D] 
/  \ 
[E]   [F] 

的A左子树的高度为3;的A右子树的高度为0。因此条件3为我们提供了3 + 0 + 1 = 4。

但是树的直径为5：EF和是E，C之间的路径上的节点，B，D,F。

由于the page you linked to解释，条件3只适用于通过树根的路径。如果两轮叶之间的最长路径不通过根，它属于条件1或2下的页面上的第一个图，甚至给出了一个例子：

右树的直径为9 ，但条件3只给出5 + 2 + 1 = 8。