测试二叉树是否平衡的时间复杂度

Question

下面的代码测试二叉树是否平衡。有人告诉我它的运行时间是O（n log n）。

据我了解...

• getHeight() 访问每个节点一次，所以它是O（n）。

• isBalanced()调用getHeight()..然后递归

如果isBalanced()在所有n个节点上调用if ，并且调用的getHeight()是O（n），为什么复杂度不是O（n²）？

int getHeight(TreeNode root) {
    if (root == null) return -1; 
    return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    int heightDiff = getHeight(root.left) - getHeight(root.right);
    if (Math.abs(heightDiff) > 1) 
        return false;
    else
        return isBalanced(root.left) && isBalanced(root.right);

}

Answer 1

n表示整个树中的节点数。在这种情况下，getHeight当您在根节点上调用该方法时，该方法仅为O（n）。通常，它是O（m），其中m是您调用的节点的子树中的节点数getHeight；而且大多数这些子树都比n小很多。这是您困惑的根本原因。

isBalanced当左和右子树的高度相差2个或更多时，该方法将尽早返回，而无需递归。因此，我们只需要为左右高度相差最多1的节点（即子树平衡的节点）计算递归调用。在最坏的情况下，所有节点的子树都是平衡的，因此我们永远都不要停止尽早递归。

鉴于此，让我们假设树是平衡的。然后getHeight每个节点调用一次，并且运行时间与该节点的子树的大小成比例。对于大小为n = 2 ^ k-1的平衡树，有：

• 2 ^（k-1）个叶节点，其子树大小为1，
• 2 ^（k-2）个大小为3的子树，
• 大小为2的2 ^（k-3）个子树
• ...
• 2 ^ i个大小为2 ^（ki）-1的子树
• ...
• 2个大小为2 ^（k-1）-1的子树
• 1个大小为2 ^ k-1 = n的子树。

这些总和是i = 0至k-1为2 ^ i *（2 ^（ki）-1）的总和。每个项大约为2 ^ k = n，并且有k = log_2 n个项，总复杂度为n * log_2 n = O（n log n）。