在 Python 中查找树节点的第 K 个祖先的程序
假设我们有一棵树,其中有 n 个节点,从 0 到 n-1 编号。树由一个父数组给出,其中 parent[i] 是节点 i 的父节点。树的根是节点 0。我们必须找到给定节点的第 k 个祖先,如果祖先不存在,则返回 -1
所以,如果输入像
那么输出将是 2,因为节点 6 的第一个祖先是 5,第二个是 2。
示例
让我们看看以下实现以更好地理解
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
以上是 在 Python 中查找树节点的第 K 个祖先的程序 的全部内容, 来源链接: utcz.com/z/363230.html