设计O(K)时间复杂度算法查找完全BST中缺失的1~2^K数值

核心思路 #

利用满二叉树的结构特性和二叉搜索树的数值分布规律，逐层判断缺失值所在的子树方向，每层仅需访问当前子树的根节点，无需遍历所有节点，最终在K步内定位缺失值。

算法步骤 #

1. 初始化参数：

   • 设当前访问节点为树的根节点 current_node
   • 设定当前数值范围的边界：low = 1，high = 2^K（K为树的层数）

2. 逐层遍历判断（共遍历K层）：

   • 计算当前数值范围的预期根节点值：expected_mid = (low + high) // 2（整数除法）
   • 比较当前节点值 current_node.val 和 expected_mid：
     • 若 current_node.val == expected_mid：
       说明左子树的数值范围[low, expected_mid-1]是完整的，缺失值在右子树。更新边界：low = expected_mid + 1，并将current_node移动到其右孩子。
     • 若 current_node.val > expected_mid：
       说明左子树的数值范围[low, expected_mid]存在缺失，导致当前节点值偏移变大。更新边界：high = expected_mid，并将current_node移动到其左孩子。
   • 重复上述操作，直到遍历完所有K层。

3. 确定缺失值：
   遍历结束后，缺失值即为最终的high（此时low与high相等）。

示例验证（K=4，缺失值14） #

• 第1层：low=1，high=16 → expected_mid=8，当前节点值=8 → 缺失值在右子树，low=9，current_node=12
• 第2层：low=9，high=16 → expected_mid=12，当前节点值=12 → 缺失值在右子树，low=13，current_node=15
• 第3层：low=13，high=16 → expected_mid=14，当前节点值=15 >14 → 缺失值在左子树，high=14，current_node=13
• 第4层：low=13，high=14 → expected_mid=13，当前节点值=13 → 遍历结束，缺失值为high=14

复杂度分析 #

• 时间复杂度：仅遍历K层，每层访问1个节点，故为O(K)
• 空间复杂度：仅使用常数级额外空间，为O(1)

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