完全二叉树的节点数

222. 完全二叉树的节点个数

中文语境和英文语境似乎有点区别，我们说的完全二叉树对应英文 Complete Binary Tree，没有问题。但是我们说的满二叉树对应英文 Perfect Binary Tree，而英文中的 Full Binary Tree 是指一棵二叉树的所有节点要么没有孩子节点，要么有两个孩子节点

完全二叉树节点数计算的复杂度

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层树(节点数大概为N)，最坏情况下

• 第一层，只有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)