पायथन में ट्री नोड के Kth पूर्वज को खोजने का कार्यक्रम

मान लीजिए कि हमारे पास n नोड्स वाला एक पेड़ है जिसकी संख्या 0 से n-1 तक है। पेड़ माता-पिता सरणी द्वारा दिया जाता है, जहां माता-पिता [i] नोड i के माता-पिता हैं। पेड़ की जड़ नोड 0 है। हमें किसी दिए गए नोड के kth पूर्वज को खोजना होगा, यदि पूर्वज मौजूद नहीं है, तो वापसी -1

तो, अगर इनपुट पसंद है

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को हल करें () परिभाषित करें। यह पैरेंट, नोड, k

  . लेगा

• यदि नोड -1 के समान है, तो

  • वापसी -1

• अन्यथा जब k 1 के समान हो, तब

  • माता-पिता को लौटाएं [नोड]

• अन्यथा जब (k और k-1) शून्य हो, तब

  • रिटर्न सॉल्व (पैरेंट, सॉल्व (पैरेंट, नोड, के / 2 का भागफल), के / 2 का भागफल)

• अन्यथा,

  • एमएसबी:=2^(के -1 के बिट्स की संख्या)

  • रिटर्न सॉल्व (पैरेंट, सॉल्व (पैरेंट, नोड, के-एमएसबी), एमएसबी)

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें

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