algorithm - 求二叉树直径的时间复杂度

Question

我在这里看到过各种计算二叉树直径的帖子。可以找到一种这样的解决方案 here (查看已接受的解决方案，而不是问题中突出显示的代码)。

我很困惑为什么代码的时间复杂度会是 O(n^2)。我不知道如何遍历树的节点两次(一次用于高度(通过 getHeight())，一次用于直径(通过 getDiameter()))是 n^2 而不是 n+n，即 2n。任何帮助将不胜感激。

Answer 1

如您所述，getHeight() 的时间复杂度为 O(n)。对于每个节点，调用函数 getHeight()。所以单个节点的复杂度是 O(n)。因此，整个算法(对于所有节点)的复杂度为 O(n*n)。