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

Question

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

据我了解...

getHeight()访问每个节点一次，所以是O(n)。
isBalanced() 调用 getHeight().. 然后递归

如果在所有n个节点上调用isBalanced()，它调用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 方法 returns 早期，不递归，当左右子树的高度相差 2 或更多时。所以我们只需要统计左右高度相差至多为1的节点，即子树平衡的节点的递归调用。在最坏的情况下，所有节点的子树都是平衡的，所以我们永远不会提前停止递归。

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

2^(k-1)个子树大小为1的叶子节点，
2^(k-2) 个大小为 3 的子树，
2^(k-3) 个大小为 7 的子树，
...
2^i 个大小为 2^(k-i) - 1 的子树，
...
2 个大小为 2^(k-1) - 1 的子树，
1 个大小为 2^k - 1 = n 的子树。

它们的总和是 i = 0 到 k-1 的 2^i * (2^(k-i) - 1) 的总和。每个项大约是 2^k = n，并且有 k = log_2 n 个项，总复杂度为 n * log_2 n = O(n log n).

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

Time complexity of testing if a binary tree is balanced

java

binary-tree

time-complexity