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

Question

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

据我了解...

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

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

如果 isBalanced() 在所有 n 个节点上调用，并且它调用 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 小很多。这是您困惑的根本原因。

当左右子树的高度相差 2 或更多时，isBalanced 方法提前返回，不递归。所以我们只需要统计左右高度相差至多为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)。