Python में ट्री नोड का Kवां पूर्वज खोजने का प्रोग्राम

मान लीजिए हमारे पास n नोड्स वाला एक ट्री है जो 0 से n-1 तक नंबर किए गए हैं। ट्री को पैरेंट ऐरे द्वारा दिया गया है, जहां parent[i] नोड i का पैरेंट है। ट्री का रूट नोड 0 है। हमें दिए गए नोड का kवां पूर्वज ढूंढना है, यदि पूर्वज मौजूद नहीं है, तो -1 वापस करें।

उदाहरण के लिए, यदि इनपुट है: तो आउटपुट 2 होगा क्योंकि नोड 6 का पहला पूर्वज 5 है और दूसरा 2 है।

समाधान के चरण

1. solve() फंक्शन परिभाषित करें जो parent, node, k लेता है
2. यदि node == -1, तो -1 वापस करें
3. अन्यथा यदि k == 1, तो parent[node] वापस करें
4. अन्यथा यदि (k & (k-1)) == 0 (अर्थात k 2 की घात है):
   • solve(parent, solve(parent, node, k >> 1), k >> 1) वापस करें
5. अन्यथा:
   • msb := 1 << (k.bit_length() - 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))

इनपुट

[-1,0,0,1,2,2,5,5], 6, 2

आउटपुट

2