如何计算完全二叉树的节点数 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：如何计算完全二叉树的节点数

评论礼仪 见这里，违者直接拉黑。

[Gipbear]

牛啊牛啊，学到了！

[z-ak-z]

或者这样， 容易理解一些：

完全二叉树节点总数是：

// 每一层都是2的(i-1)次幂
int res = 0;
for (int i = 1; i <= lo;i++) {
    res += Math.pow(2, i - 1);
}
return res;

[Fjyyyyy]

?

[ping2h]

?

[KairongChen-l]

？

[TimurJiangShan]

算法的时间复杂度怎么算的呀， 每次递归的复杂度是while循环（logN）， 最后return的那个递归只有一个会被执行，因此return的复杂度相当于递归内容的复杂度（while循环logN）， 最后相乘？

[labuladong]

递归的次数 x 每次递归的时间复杂度，递归次数就是树的高度 O(logN)，每次递归所花费的时间就是 while 循环，需要 O(logN)，所以总体的时间复杂度是 O(logN*logN)。

[Xiazeyu0628]

dong哥的解释很详细

[happy2h]

确实吊

[strickland0702]

代码注释有个小错误，代码中的lh和rh代表的并不是左右子树的高度，而是一直沿最左和最右走的长度，如果lh == rh, 则说明完全二叉树是满二叉树。

[labuladong]

@strickland0702 明白你的意思了，有道理，我改下表述

[d0odLe]

看评论区没有说，我来说一下单纯计数的那一部分，没有返回0是怎么计算的，望斧正

按理说如果是单纯计数，到了null结点需要返回0，而东哥的代码并没有显式的返回0，其实已经囊括在

if (hl == hr) {
    return (int)Math.pow(2, hl) - 1;
}

这部分中，若是只有左右子树中的一个，比如左子树只有一个，右子树为空，
左子树：hl == hr == 1 --> return (int)Math.pow(2, hl) - 1 == 1，
右子树：hl == hr == 0 --> return (int)Math.pow(2, hl) - 1 == 0。

[LebronHarden1]

乖乖,又长见识了

[zhangpanzhan]

我能理解你说的计算那部分full tree的计算,,但是另一半呢? 就是总有一条路径只有左孩子,没有右孩子的,不得还是一种naive的方式.我的理解是, 这条路径其实就是单独算, 复杂度是O(h)

[lhcezx]

东哥我没理解非满二叉树子树的递归复杂度计算。对于满二叉树的子树遍历中有两个while，按照层数从上到下高度为log(n)因此复杂度为O(logn)没毛病，非满二叉树的子树相当于需要遍历该子树中的每一个节点吧？感觉递归次数并不是树的高度而是子树中节点的数目，递归函数每次执行的复杂度为O(logn)，节点数目准确来说应该是N / 2 (因为子树包含一半的节点)， 因此复杂度不应该是O(logn * n / 2)嘛？
如果我说的不对麻烦大佬指正，没太明白怎么计算出的log^2(n)

[labuladong]

非满二叉树的子树相当于需要遍历该子树中的每一个节点吧

@lhcezx 你说的这句话不对。注意代码，非满二叉树也只需要从根节点走到叶子节点，即遍历「高度」而不是「所有节点」，所以所需时间就是 logN，因此结果就是 O(logN*logN)。

[deepbreath373]

check in

[Goolloo]

1. Complete BT必然从root开始，有一半是perfect BT(O(logN))，另一半可能也是perfect BT或者Complete BT
2. 如果是Complete BT，那么又回到上一层的逻辑——即一半子树是perfect BT，另一半是Complete BT
3. 那么最坏的情况下就是，每一层都是一半是perfect BT，另一半半complete BT。并且你需要继续去下一层去计算complete BT的那一半子树。
4. 那么最多需要计算几次这种一半子树呢？就是整个树的深度/高度——O(logN)。每次计算量是多少呢？O(logN)。所以总的计算量是O((logN)^2)

举例子算一下，如果6层树，最坏情况下

• 第一层，只有root
• 第二层，一半是perfect BT，O(logN)，另一半需要在第三层分左右子树计算
• 第三层，一半是perfect BT，O(logN)，另一半需要在第四层分左右子树计算
• 第四层，一半是perfect BT，O(logN)，另一半需要在第五层分左右子树计算
• 第五层，一半是perfect BT，O(logN)，另一半需要在第六层分左右子树计算
• 第六层，是最后一层，怎么都是perfect BT，O(logN)

总计算量就是

O() = 5*O(logN) = (O(logN)-1)*O(logN) = O(logN)*O(logN) = O((logN)^2)

[labuladong]

👍

[LeeHaruYa]

滴滴滴打卡

[yonggui-yan]

打卡

”完全二叉树的左右两边，总有一个是满的“ 有趣

[jxs1211]

go version

func countNodes(root *TreeNode) int {
    if root == nil {return 0}
    l := 0
    left := root
    for left != nil {
        left = left.Left
        l++ 
    }
    r := 0
    right := root
    for right != nil {
        right = right.Right
        r++ 
    }
    if l == r {
        return int(math.Pow(2, float64(l)) - 1)
    }
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}

[GoingMyWay]

看了那么多回答，计算复杂度的结果我还是没看懂>_<||

[hanleilei]

直接上DFS的preorder呢？

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        self.c = 0

        def preorder(node):
            if node:
                self.c += 1
                preorder(node.left)
                preorder(node.right)
        preorder(root)
        return self.c

[5Reasons]

JavaScript 版本

var countNodes = function(root) {
    // 比较有趣的思路：顶部的部分 用full二叉树的做法来做
    // 最下面一层 用正常二叉树的思路来做？
    let l = root,r = root
    let leftH = 0,rightH = 0
    // 计算左侧高度
    while(l!=null){
        l = l.left
        leftH++
    }
    // 计算右侧高度
    while(r!=null){
        r = r.right
        rightH++
    }
    // 如果高度相等，满二叉树
    if(leftH == rightH){
        return Math.pow(2,leftH)-1 // 这个实际上也充当了 base case 的角色
    }
    // 如果高度不相等，进行正常计算
    return 1 + countNodes(root.left) + countNodes(root.right)
};

[alfvn]

「完全二叉树比普通二叉树特殊，但又没有满二叉树那么特殊」
观察它的每棵子树，它特殊的地方到底在哪？就是它有一半必定是满二叉树，另一半是完全二叉树。那如果我们能确定哪一半是满二叉树，这棵子树就不需要遍历去统计节点了，只需要用数学公式返回它的值即可。这样，就省了一半的功夫。其实是二分的逻辑，只有一半是需要继续递归的，然后，我们有一个问题还没有处理，那就是我们怎么判断以当前节点为根的二叉树是不是满二叉树？我们沿着最左侧和最右侧计算高度，高度一致就是满二叉树，这里正需要用到这个算法。我们确定是满二叉树还是完全二叉树要花O(logN)时间。因此，总的时间复杂度就是 O(logN) * O(logN)

[alfvn]

「那就是我们怎么判断以当前节点为根的二叉树是不是满二叉树？我们沿着最左侧和最右侧计算高度，高度一致就是满二叉树」这里错了，是判断完全二叉树是不是满二叉树，而不是普通二叉树是不是满二叉树

[tingtingwang217]

东哥牛！

[protectione055]

妙啊

[qizidev]

感觉复杂度如果用 O(log(N/2) + log(N/4) + .... + 1) 去表示可能更好理解些，完全二叉树的左右子树递归的去看的话，一定有一半是满二叉树，只有最后的一个枝叶是普通二叉树，那就是可以近似有 log(N) 个完全二叉树的递归，每一个log(N/xxx)可以近似成 log(N)，那么 O(log(N/2) + log(N/4) + .... + 1) = O(log(N)*log(N)) 了

[YaoKong]

看了一圈你的最好理解

[CodeLife2012]

感觉算法的复杂度分析不太严谨，没有数学上的证明;不过严格证明就麻烦了

[DavidingPlus]

巧妙！