如何在低于O(n)时间复杂度下查找完全二叉树节点的中序遍历位置

问题描述 #

给定一棵完全二叉树的某个节点n，可获取以下三类信息：

• 以节点n为根的子树的节点数量
• 节点n的父节点
• 节点n的直接子节点
  需要找出节点n在该完全二叉树中序遍历中的位置（采用1-based索引）。

示例二叉树：

0
     /   \
    1     2
   / \   / \
  3   4 5   6

在该树中，节点2的中序遍历位置为6，节点6的位置为7。

结论与实现思路 #

可以在O(logN)（低于线性时间）的复杂度下得到答案，具体思路如下：

1. 初始计算：先获取节点n的左子树节点数left_cnt，那么n在自身子树的中序位置为 left_cnt + 1（中序遍历左子树优先，左子树所有节点都在n之前）。
2. 向上回溯父节点：从n开始依次向上遍历父节点，根据当前节点是父节点的左/右子节点，调整位置值：
   • 如果当前节点是父节点的右子节点：父节点的左子树所有节点（记为left_sub_size）加上父节点自身，都在当前节点的遍历序列之前，因此需要将当前位置加上 left_sub_size + 1。
   • 如果当前节点是父节点的左子节点：无需额外累加，直接继续向上回溯即可。
3. 终止条件：当回溯到根节点时，最终的位置值就是节点n在整棵树中的中序遍历位置。

示例验证 #

• 节点2的计算过程：
  1. 节点2的左子树节点数为1（仅节点5），自身子树内位置为1+1=2。
  2. 节点2是根节点0的右子节点，根节点0的左子树节点数为3（节点1、3、4），累加3+1=4，最终位置为2+4=6，与示例一致。
• 节点6的计算过程：
  1. 节点6是叶子节点，左子树节点数为0，自身子树内位置为0+1=1。
  2. 节点6是节点2的右子节点，节点2的左子树节点数为1，累加1+1=2，当前位置变为1+2=3。
  3. 节点2是根节点0的右子节点，累加3+1=4，最终位置为3+4=7，与示例一致。

由于完全二叉树的高度为O(logN)，每一步回溯仅需O(1)操作，因此整体时间复杂度为O(logN)，远低于线性时间O(N)。

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