已知完全二叉树总节点数求左右子树节点数的O(1)解法

存在可以直接套用的计算公式，整体时间复杂度可以做到O(1)，推导和使用方法如下： #

推导逻辑 #

完全二叉树的结构特性是：除了最后一层，其余所有层都是满节点，最后一层的节点全部靠左排列。基于这个特性我们可以拆分总节点数计算：

1. 先计算整棵树的高度h（根节点算第1层）：h = floor(log₂(n)) + 1，floor表示向下取整
2. 前h-1层是满二叉树，总节点数为：full = 2^(h-1) - 1
3. 最后一层的实际节点数为：last = n - full
4. 根节点的左子树最多能容纳的最后一层节点数为：left_max_last = 2^(h-2)
5. 分两种情况计算左右子树节点数：
   • 当最后一层节点数不超过左子树可容纳上限时：
     左子树节点数 = (2^(h-2) - 1) + last
     右子树节点数 = 2^(h-2) - 1
   • 当最后一层节点数超过左子树可容纳上限时：
     左子树节点数 = 2^(h-1) - 1
     右子树节点数 = (2^(h-2) - 1) + (last - left_max_last)

示例验证 #

你给出的测试用例完全符合公式计算结果：

• 总节点数n=5：
  h = floor(log₂5) +1 = 2+1=3，full=2^2 -1=3，last=5-3=2，left_max_last=2^(3-2)=2
  满足last <= left_max_last，左子树节点数= (2^1 -1)+2=3，右子树节点数=2^1 -1=1，和示例一致。
• 总节点数n=8：
  h = floor(log₂8)+1=3+1=4，full=2^3 -1=7，last=8-7=1，left_max_last=2^(4-2)=4
  满足last <= left_max_last，左子树节点数= (2^2 -1)+1=4，右子树节点数=2^2 -1=3，和示例一致。

O(1)实现说明 #

公式中的floor(log₂(n))不需要用循环或者浮点对数运算，现代CPU都有内置的位运算指令，可以直接获取整数的最高有效位位置，所有编程语言基本都有对应的内置函数实现，比如32位无符号整数场景下：

• C/C++：31 - __builtin_clz(n)
• Java：31 - Integer.numberOfLeadingZeros(n)
• Python：n.bit_length() -1
  整体计算过程没有循环，所有操作都是单指令完成，时间复杂度严格为O(1)。

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