資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告