fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
如何计算完全二叉树的节点数 :: labuladong的算法小抄
或者这样， 容易理解一些：
完全二叉树节点总数是：
// 每一层都是2的(i-1)次幂
int res = 0;
for (int i = 1; i <= lo;i++) {
res += Math.pow(2, i - 1);
}
return res;
算法的时间复杂度怎么算的呀， 每次递归的复杂度是while循环（logN）， 最后return的那个递归只有一个会被执行，因此return的复杂度相当于递归内容的复杂度（while循环logN）， 最后相乘？
递归的次数 x 每次递归的时间复杂度，递归次数就是树的高度 O(logN)，每次递归所花费的时间就是 while 循环，需要 O(logN)，所以总体的时间复杂度是 O(logN*logN)。
代码注释有个小错误，代码中的lh和rh代表的并不是左右子树的高度，而是一直沿最左和最右走的长度，如果lh == rh, 则说明完全二叉树是满二叉树。
看评论区没有说，我来说一下单纯计数的那一部分，没有返回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。
我能理解你说的计算那部分full tree的计算,,但是另一半呢? 就是总有一条路径只有左孩子,没有右孩子的,不得还是一种naive的方式.我的理解是, 这条路径其实就是单独算, 复杂度是O(h)
东哥我没理解非满二叉树子树的递归复杂度计算。对于满二叉树的子树遍历中有两个while，按照层数从上到下高度为log(n)因此复杂度为O(logn)没毛病，非满二叉树的子树相当于需要遍历该子树中的每一个节点吧？感觉递归次数并不是树的高度而是子树中节点的数目，递归函数每次执行的复杂度为O(logn)，节点数目准确来说应该是N / 2 (因为子树包含一半的节点)， 因此复杂度不应该是O(logn * n / 2)嘛？ 如果我说的不对麻烦大佬指正，没太明白怎么计算出的log^2(n)
非满二叉树的子树相当于需要遍历该子树中的每一个节点吧
@lhcezx 你说的这句话不对。注意代码，非满二叉树也只需要从根节点走到叶子节点，即遍历「高度」而不是「所有节点」，所以所需时间就是 logN，因此结果就是 O(logN*logN)。
- Complete BT必然从root开始，有一半是perfect BT(O(logN))，另一半可能也是perfect BT或者Complete BT
- 如果是Complete BT，那么又回到上一层的逻辑——即一半子树是perfect BT，另一半是Complete BT
- 那么最坏的情况下就是，每一层都是一半是perfect BT，另一半半complete BT。并且你需要继续去下一层去计算complete BT的那一半子树。
- 那么最多需要计算几次这种一半子树呢？就是整个树的深度/高度——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)
