在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]
- 返回parent[node]
否则，当（k AND k-1）为零时，
- return solve(parent, solve(parent, node, k/2的商) , k/2的商)
否则，
- msb：= 2 ^（k-1位数）
- return 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))