数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找树节点的第K个祖先节点
假设我们有一棵包含n个节点的树，节点编号从0到n-1。这棵树由一个父节点数组给出，其中parent[i]是节点i的父节点。树的根节点是节点0。我们需要找到给定节点的第k个祖先节点，如果祖先节点不存在，则返回-1。
例如，输入如下：
则输出为2，因为节点6的第一个祖先节点是5，第二个祖先节点是2。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数solve()。它将接收parent，node，k作为参数。
如果node等于-1，则
返回-1
否则，如果k等于1，则
返回parent[node]
否则，如果(k AND k-1)为零，则
返回solve(parent, solve(parent, node, k/2的商) , k/2的商)
否则，
msb := 2^(k的位数 -1)
返回solve(parent, solve(parent, node, k-msb) , msb)
示例
让我们来看下面的实现以更好地理解。
def solve(parent, node, k):
if node == -1:
return -1
elif k == 1:
return parent[node]
elif not (k & k-1):
return solve(parent, solve(parent, node, k >> 1), k >> 1)
else:
msb = 1 << (k.bit_length()-1)
return solve(parent, solve(parent, node, k-msb), msb)
parent = [-1,0,0,1,2,2,5,5]
node = 6
k = 2
print(solve(parent, node, k))输入
[6,7,9,16,22], 2
输出
2
更新于：2021年10月6日
320 次浏览
广告