如何处理不确定层数的循环？二叉树节点路径可达性判断求助

数据老陈

2026-8-6

二叉树节点可达性判断优化方案

利用完全二叉树的数学性质直接判断（最优方案）

你生成的是完全二叉树结构，每个节点x的左子节点为2*x，右子节点为2*x+1。判断x能否向下到达y，无需遍历所有路径，只需反向推导y的父节点链：

由于y > x，循环将y替换为其父节点（y = y // 2）
每次替换后检查是否等于x，若在y减小到≤x前匹配成功，说明存在路径；反之则不存在

示例代码：

def is_reachable(x, y):
    while y > x:
        y = y // 2
        if y == x:
            return True
    return False

# 测试示例
print(is_reachable(1, 4))  # 输出True（1→2→4）
print(is_reachable(2, 7))  # 输出False（7的父链是3→1，无法到达2）
print(is_reachable(3, 6))  # 输出True（3→6）

预处理祖先集合（适合批量查询）

如果要处理1000次查询，可提前预处理每个节点的所有祖先并存储为集合，查询时直接判断x是否在y的祖先集合中：

# 假设二叉树最大节点数为n
n = 1000
ancestors = {}

for y in range(1, n + 1):
    ancestors[y] = set()
    current = y // 2
    while current >= 1:
        ancestors[y].add(current)
        current = current // 2

# 查询函数
def is_reachable(x, y):
    return x in ancestors.get(y, set())

预处理仅需一次，后续每次查询均为O(1)时间，适合高频查询场景。