在面试中，被问及如何判断一棵完全二叉树中序号为p和q的两个节点是否位于同一层，是一个考察对完全二叉树性质理解以及算法设计能力的问题。作为高级程序员，我们不仅要能准确回答问题，还要能够优雅地通过代码实现这一逻辑，同时展现出对数据结构深层次的理解。 ### 完全二叉树的性质 首先，我们需要明确完全二叉树的定义及其性质。完全二叉树是一种特殊的二叉树，其中除了最后一层外，每一层都被完全填满，并且所有节点都尽可能地向左对齐。在完全二叉树中，节点的序号（或称为索引）通常从1开始，并且遵循以下规律： - 对于任意节点i（i > 1），其父节点的序号为 `i / 2`（整数除法）。 - 对于节点i的左子节点，若存在，其序号为 `2 * i`。 - 对于节点i的右子节点，若存在，其序号为 `2 * i + 1`。 ### 判定逻辑 要判断序号为p和q的两个节点是否在同一层，最直接的方法是计算它们各自的深度（即它们到根节点的路径上边的数量），然后比较这两个深度是否相等。然而，在完全二叉树中，我们可以利用序号的性质来更高效地实现这一点。 由于完全二叉树的特性，同一层的节点序号在二进制表示下，除了最高位（可能由于树的总层数不同而不同）外，其余位都相同。但直接进行二进制操作可能会稍显复杂，且不是最直接的方法。更简洁的思路是，我们可以观察到，对于任意一层的节点，其序号总是连续的一段区间，且这个区间的起始和结束节点可以通过层数直接计算出来（尽管这里我们并不直接计算层数）。 一个更高效的方法是，通过计算p和q的“层内序号”（即在同一层内，相对于该层起始节点的偏移量），然后比较这两个层内序号是否在同一层的有效范围内。不过，由于直接计算层内序号需要知道层数，而题目并未直接给出层数的计算方式，我们可以采用一个折中的方法：利用完全二叉树的性质，通过不断除以2并比较余数来间接判断。 ### 示例代码 虽然直接通过层内序号判断更为直观，但在这里，我将展示一个基于完全二叉树性质，通过不断向上追溯至同一祖先节点（不一定是直接父节点），然后检查p和q在向上追溯过程中是否始终保持在同一侧（左或右）的方法。这种方法虽不直接计算层内序号，但能有效判定节点是否在同一层。 ```python def are_on_same_level(p, q): # 确保p和q均为正整数 if p <= 0 or q <= 0: return False # 当p和q相等时，显然在同一层 if p == q: return True # 使用队列进行层序遍历的模拟，但实际上我们只需要检查p和q的祖先路径 while p != 1 and q != 1: # 检查p和q的父节点是否在同一侧 if (p % 2 == 0) != (q % 2 == 0): # 如果p和q一奇一偶，则不在同一侧 return False # 向上移动到父节点 p //= 2 q //= 2 # 如果p和q都回到了根节点（1），但它们之前不在同一侧，则不在同一层 return (p == 1) and (q == 1) # 示例 print(are_on_same_level(3, 4)) # False, 因为3在左子树，4在右子树 print(are_on_same_level(3, 6)) # True, 因为它们在同一层 ``` 注意：上述代码通过检查p和q在向上追溯过程中是否始终在同一侧（即p和q的奇偶性始终保持一致）来间接判断它们是否在同一层。这种方法避免了直接计算层数的复杂性，但依赖于完全二叉树的性质。 ### 总结 在面试中，对于这类问题，除了给出正确的解决方案外，更重要的是要能够清晰地解释你的思路，并展示你对数据结构和算法设计的深入理解。同时，通过编写简洁、高效的代码来验证你的想法，也是展现你作为高级程序员能力的关键。在码小课网站上分享这样的面试问题及解决方案，不仅能帮助自己巩固知识，也能为其他学习者提供有价值的参考。