二叉树的直径 - 算法复杂度

Question

在 another question 关于找到计算二叉树直径的算法中，提供了以下代码作为问题的可能答案。

public static int getDiameter(BinaryTreeNode root) {        
    if (root == null)
        return 0;

    int rootDiameter = getHeight(root.getLeft()) + getHeight(root.getRight()) + 1;
    int leftDiameter = getDiameter(root.getLeft());
    int rightDiameter = getDiameter(root.getRight());

    return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
}

public static int getHeight(BinaryTreeNode root) {
    if (root == null)
        return 0;

    return Math.max(getHeight(root.getLeft()), getHeight(root.getRight())) + 1;
}

评论区说上面代码的时间复杂度是O(n^2)。在给定的 getDiameter 函数调用中，会为左右子树调用 getHeight 和 getDiameter 函数。

让我们考虑二叉树的平均情况。高度可以在 Θ(n) 时间计算（对于最坏的情况也是如此）。那么我们如何计算 getDiameter 函数的时间复杂度呢？

我的两个理论

Τ(n) = 4T(n/2) + Θ(1) = Θ(n^2)，考虑高度计算（相同？）子问题。
T(n) = 2T(n/2) + n + Θ(1) = Θ(nlogn), n = 2*n/2 用于高度计算？

感谢您的时间和精力！

Answer 1

混淆的一点是你认为二叉树是平衡的。实际上，它可以是一条线。在这种情况下，我们需要从根到叶子的n操作来找到高度，从根的child到叶子的n - 1操作等等。这给出了 O(n^2) 操作来单独查找所有节点的高度。

如果在找到直径之前独立计算每个节点的高度，则可以优化算法。然后我们将花费 O(n) 时间来找到所有高度。那么找到直径的复杂性将是以下类型：

T(n) = T(a) + T(n - 1 - a) + 1

其中 a 是左子树的大小。这种关系也会给出寻找直径的线性时间。所以总时间是线性的。

二叉树的直径 - 算法复杂度

Diameter of Binary Tree - Algorithm Complexity

algorithm

binary-tree

time-complexity