完全二叉树节点计数算法的时间与空间复杂度分析

算法代码 #

public int countNodes(TreeNode root) {
    if(root==null){
        return 0;
    }
    int LH=height(root,false); // 最左叶子节点深度
    int RH=height(root,true);  // 最右叶子节点深度
    if(LH==RH){
        return (int)Math.pow(2,LH)-1;
    }
    else return countNodes(root.left)+countNodes(root.right)+1;
}

int height(TreeNode root,boolean lr){
    if(root==null)
        return 0;
    if(lr==false)
        return 1+height(root.left,lr);
    return 1+height(root.right,lr);
}

问题 #

这段代码无需遍历所有节点即可计算完全二叉树的节点数量，但由于部分节点会被多次访问，如何确定该算法的时间复杂度？

完全二叉树：除最底层节点外，其余所有层的节点都被完全填满，最底层节点尽可能靠左填充

时间复杂度分析 #

核心逻辑

算法利用完全二叉树的特性做优化：如果某个子树的最左深度等于最右深度，说明这是满二叉树，直接用公式2^深度 - 1计算节点数，无需递归遍历；若深度不等，则递归处理左右子树。

推导过程

1. 单次高度计算的成本：不管是计算最左还是最右深度，都是沿着树的单边路径走到底，时间复杂度为O(log n)——因为完全二叉树的高度是log₂(n)级别（n为总节点数）。
2. 递归的触发次数：递归仅在左右子树深度不等时发生，而完全二叉树的特性决定了，每一层最多只有一个子树需要继续递归（另一个子树必然是满二叉树，直接用公式计算）。递归的最大深度等于树的高度，即O(log n)。
3. 总时间复杂度：每轮递归需要两次O(log n)的高度计算，加上递归的对数级深度，总时间为O((log n)²)。

换个角度量化：假设树的高度为h，第一次高度计算耗时h；若需递归，其中一个子树的高度计算耗时h-1，依此类推直到递归终止。总耗时为h + (h-1) + (h-2) + ... + 1 = h(h+1)/2，而h = log₂(n)，代入后就是O((log n)²)。

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