algorithm - 在计算树的直径时，为什么仅计算高度是不够的

Question

在计算树的直径时，我们会考虑以下各项中的最大值:

1:左子树的直径

2:右子树的直径

3:左子树的高度+右子树的高度+1。

为什么这三个是必要的？为什么 3. 单独是不够的。让我们以 3 节点树和 2 节点树为例。在前第三点中，仅给出 1 + 1 + 1 = 3。 而在后一种情况下，仅第 3 个点给出 0 + 1 + 1 = 2。

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

Answer 1

考虑下面的树:

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

A的左子树高度为3； A 右子树的高度为 0。因此条件 3 给出 3 + 0 + 1 = 4。

但是树的直径是5:E和F之间路径上的节点是E,C, B, D, F.

作为the page you linked to解释说，条件 3 仅适用于通过树根的路径。如果两片叶子之间的最长路径不通过根，则它属于条件 1 或 2。该页面上的第一个图甚至显示了一个示例:

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