โปรแกรมหาบรรพบุรุษที่ k ของโหนดในต้นไม้ใน Python

ปัญหา

ต้นไม้ n โหนด (0 ถึง n-1) กำหนดโดยอาร์เรย์ parent ที่ parent[i] คือพ่อของ i รากคือ 0 หาบรรพบุรุษที่ k ของโหนดที่กำหนด ถ้าไม่มีคืน -1

ตัวอย่าง

parent = [-1,0,0,1,2,2,5,5], node=6, k=2 → ผลลัพธ์ 2 (บรรพบุรุษที่ 1 คือ 5, ที่ 2 คือ 2)

ขั้นตอนการแก้ปัญหา

1. ถ้า node == -1: คืน -1
2. ถ้า k == 1: คืน parent[node]
3. ถ้า k เป็นกำลังของ 2 (i.e. k & (k-1) == 0):
   • คืน solve(parent, solve(parent, node, k//2), k//2)
4. มิฉะนั้น:
   • msb := 1 << (k.bit_length() - 1)
   • คืน solve(parent, solve(parent, node, k-msb), msb)

การนำไปใช้งาน (Python)

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