如何确定0基索引完全二叉树中指定子树的叶子节点索引

解法说明 #

题目给出的是0基索引的满二叉树（完全二叉树的特殊形态），所有叶子均分布在最后一层，可按以下方法快速计算任意节点对应子树的叶子索引范围：

前置约定 #

我们约定根节点为第0层，设整个树的叶子所在层为L（题目示例中叶子在第3层，即L=3）：

• 叶子层起始索引：leaf_start = (1 << L) - 1（即2^L - 1，示例中为7）
• 叶子层结束索引：leaf_end = (1 << (L+1)) - 2（示例中为14）

计算步骤（输入任意节点索引i） #

1. 计算节点i所在的层数k
   公式：k = floor(log2(i + 1))，也可以直接通过二进制判断：i+1的二进制最高位的位置减1就是k。
2. 计算节点i在当前层的偏移量offset
   公式：offset = i - ((1 << k) - 1)，即该节点是所在层的第offset个节点（从0开始计数）。
3. 计算子树覆盖的叶子数量span
   从节点i所在层到叶子层的层数差为d = L - k，则该子树共包含span = 1 << d（即2^d）个叶子节点。
4. 计算叶子索引范围
   子树第一个叶子索引：start = leaf_start + offset * span
   子树最后一个叶子索引：end = start + span - 1
   最终结果就是闭区间[start, end]内的所有整数。

示例验证 #

完全匹配题目给出的测试用例：

• 当i = 0时：start=7、end=14，结果为7、8…14
• 当i = 1时：start=7、end=10，结果为7、8、9、10
• 当i = 4时：start=9、end=10，结果为9、10

扩展说明 #

如果是普通非满的完全二叉树，只需要最后将计算得到的end和整棵树的最大节点索引取最小值，避免索引越界即可。

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