สมมติว่าเรามีต้นไม้ที่มี n โหนดที่มีหมายเลขตั้งแต่ 0 ถึง n-1 ต้นไม้ถูกกำหนดโดยอาร์เรย์หลัก โดยที่ parent[i] คือพาเรนต์ของโหนด i รากของต้นไม้คือโหนด 0 เราต้องหาบรรพบุรุษที่ k ของโหนดที่ระบุ ถ้าไม่มีบรรพบุรุษอยู่ ให้คืนค่า -1
ดังนั้นหากอินพุตเป็นแบบ
ผลลัพธ์จะเป็น 2 เพราะบรรพบุรุษแรกของโหนด 6 คือ 5 และที่สองคือ 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน Solve() นี่จะนำพาเรนต์, โหนด, k
-
ถ้าโหนดเหมือนกับ -1 แล้ว
-
กลับ -1
-
-
มิฉะนั้นเมื่อ k เท่ากับ 1 แล้ว
-
ส่งคืนพาเรนต์[โหนด]
-
-
มิฉะนั้นเมื่อ (k AND k-1) เป็นศูนย์ ดังนั้น
-
ผลตอบแทนการแก้ (พาเรนต์, แก้ปัญหา (พาเรนต์, โหนด, ผลหารของ k/2) , ผลหารของ k/2)
-
-
มิฉะนั้น
-
msb :=2^(จำนวนบิตของ k -1)
-
คืนค่าการแก้ (พาเรนต์, แก้ปัญหา (พาเรนต์, โหนด, 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
