java - 解释一下为什么这个二叉树遍历算法的时间复杂度是O(NlogN)？

Question

我现在正在阅读 Cracking the Coding Interview 一书，并且正在做一个二叉树练习。根据 O(NlogN) 一书，有一段代码，但是，我不明白为什么会这样。我能理解算法是否为 O(N)，但我不知道 logN 在他们的分析中来自何处。

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

boolean isBalanced(TreeNode root) {
    if (root == null) return true; // Base case

    int heightDiff = getHeight(root.left) - getHeight(root.right);
    if (Math.abs(heightDiff) > 1) {
        return false;
    } else { 
        // Recurse
        return isBalanced(root.left) && isBalanced(root.right);
    }
}

Answer 1

如果我们遇到一个不平衡的节点，我们会提前返回 false，所以这是最佳情况。该算法要处理的“最坏情况”是一棵完全平衡的树，因为我们没有得到 false 的早期返回。为了这个例子，让我们使用一个有 n 个节点的完美二叉树。

第一次调用将在每个节点上触发 getHeight()，因此将访问 ~n 个节点。根级别的总工作量为 O(n)。

接下来的两个调用(root.left.isBalanced() 和 root.right.isBalanced())将在后续节点上触发 getHeight()，但每个调用仅在 ~1/2 n 个节点上调用它。 1 个高度的总工作量也是 O(n)。

接下来的 4 次调用将分别在 n/4 个节点上调用 getHeight。所以 2 高度的总工作量也是 O(n)。

如果你看到这个模式，树的每个级别的总工作量是 O(n)，所以所有级别的总工作量是 O(n) * 完美树中的级别，结果是 O(nlogn) .