完全二叉树节点计数算法：最坏时间复杂度疑惑解析

我正在研究LeetCode第222题《Count Complete Tree Nodes》，题目要求如下：

给定一棵完全二叉树的根节点root，返回树中节点的总数。
根据维基百科定义，完全二叉树除最后一层外，每一层都被完全填满，且最后一层的所有节点尽可能靠左。最后一层h的节点数范围是1到2^h。
需设计时间复杂度小于O(n)的算法。

我原本期望算法达到O(log(n))的时间复杂度，但我认为最坏情况（最后一层仅含一个节点）时，该算法的时间复杂度会是O(n*log(n))，这不符合小于O(n)的要求。我哪里理解错了？

分析 #

通用的暴力解法是遍历整棵树统计节点数，时间复杂度为O(n)，其中n为节点总数。

为优化效率，我们可以利用完全二叉树的特性（树的层数为O(log(n))），计算子树的左高度和右高度。若某子树的左右高度相等，则该子树是满二叉树，节点数可通过公式2^h - 1计算（h为子树高度）。

对应的代码如下：

int findLeftHeight(BinaryTreeNode<int>* root){
    int leftHeight = 0;
    while(root){
        leftHeight += 1;
        root = root->left;
    }
    return leftHeight;
}

int findRightHeight(BinaryTreeNode<int>* root){
    int rightHeight = 0;
    while(root){
        rightHeight += 1;
        root = root->right;
    }
    return rightHeight;
}

int countCompleteNodes(BinaryTreeNode<int>* root){
    if(root == NULL){
        return 0;
    }
    int lh = findLeftHeight(root);
    int rh = findRightHeight(root);

    if(lh == rh) return (1<<lh)-1;

    return 1 + countCompleteNodes(root->left) + countCompleteNodes(root->right);
}

但在最坏情况（完全二叉树最后一层仅有一个节点，且层数达到n对应的最大层数）时，我认为每次递归都会同时调用root->left和root->right，导致时间复杂度为O(n*log(n))。我究竟忽略了什么？

解答 #

你忽略了完全二叉树的核心特性在递归过程中的作用：每次递归只会对左右子树中的一个进行深度递归，另一个子树必然是满二叉树，可以直接通过公式计算节点数，无需继续递归。

以你说的最坏情况为例：最后一层只有最左侧一个节点。此时根节点的左高度lh比右高度rh大1，所以进入递归分支。但此时根节点的右子树一定是一棵满二叉树（因为完全二叉树最后一层节点靠左，右子树的所有层都被填满），所以计算右子树时，它的左右高度相等，直接返回2^rh -1，不会再递归右子树的子节点。

而左子树的情况和原树类似：最后一层可能也只有一个节点，同样的逻辑，递归左子树时，它的右子树又是满二叉树，直接计算，只需要递归左子树的左子节点。

整个递归过程的深度是O(logn)（树的高度），而每一层递归中，计算左右高度的时间是O(logn)，总的时间复杂度是O((logn)^2)，这显然小于O(n)（当n足够大时，(logn)^2远小于n）。

举个具体的例子：假设树的高度是h，那么递归的次数是h次，每次计算高度需要h、h-1、h-2...1次操作，总和是h*(h+1)/2，而h=log₂(n)，所以总时间是O((logn)^2)，完全符合题目要求。

内容的提问来源于stack exchange，提问作者Paras Khosla