高度为h的完全二叉树如何查找h个满足约束的不相关分区

前置约定 #

我们先明确高度定义：高度为h的完全二叉树，根节点为第1层，最远叶子节点在第h层，根节点不纳入任何分区。

实现步骤 #

步骤1：层序遍历收集所有非根节点 #

按从上到下、同层从左到右的顺序遍历整棵树，跳过根节点，得到节点列表node_list。层序遍历的特性保证了所有父节点一定出现在它的子节点之前。

步骤2：循环分配节点到h个分区 #

初始化h个空分区，遍历node_list中的第i个节点（下标从0开始），将其分配到第i % h个分区中。
这个分配逻辑天然满足所有约束：

• 满足约束1（无直接父子同分区）：完全二叉树任意父节点和它的两个子节点在node_list中的下标差至少为2^(i-1) - 1（i为父节点所在层号），当h≥2时，下标差远大于h，不可能被分到同一个i%h的分区里。
• 满足约束2（分区大小差不超过1）：循环分配的模式本身就会把节点平均分配到各个分区，最多只有1个节点的数量差。
• 满足约束3（根节点不纳入）：遍历的时候直接跳过了根节点，不会进入分配流程。

步骤3：可选校验 #

如果需要额外确认，可以遍历每个分区，检查是否存在直接父子节点对，若存在（极端小h场景下的小概率情况），只需将冲突的子节点调整到相邻的分区即可，不会破坏数量差约束。

示例验证（h=3的情况） #

高度为3的完全二叉树，非根节点有6个，要分3个分区：

• node_list按层序是：[2层左，2层右，3层左1，3层左2，3层右1，3层右2]
• 分配后：
  • 分区0：2层左，3层左2
  • 分区1：2层右，3层右1
  • 分区2：3层左1，3层右2
• 校验：每个分区没有直接父子，每个分区都是2个节点，差值为0，根节点未纳入，完全符合要求。

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