解释为什么这个二叉树遍历算法的时间复杂度为 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)。