एक पूर्वज को खोजने का कार्यक्रम जो पायथन में एक बाइनरी ट्री में दो तत्वों में से एक है

मान लीजिए कि हमारे पास एक बाइनरी ट्री है, और हमारे पास दो नंबर ए और बी भी हैं, हमें सबसे कम नोड का मान ज्ञात करना है जिसमें ए और बी वंशज हैं। हमें यह ध्यान रखना होगा कि एक नोड स्वयं का वंशज हो सकता है।

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

a =6, b =2, तो आउटपुट 4 होगा

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

• एक विधि को परिभाषित करें हल करें () यह जड़ लेगा और a, b

• अगर रूट शून्य है, तो

  • वापसी -1

• यदि रूट का मान या तो a या b है, तो

  • रूट का रिटर्न वैल्यू

• बायां:=हल करें (रूट के बाएं, ए, बी)

• दाएं:=हल करें (रूट का अधिकार, ए, बी)

• अगर बाएँ या दाएँ -1 नहीं है, तो

  • रूट का रिटर्न वैल्यू

• बाएं लौटें अगर बाएं -1 के समान नहीं है अन्यथा दाएं

• मुख्य विधि से कॉल सॉल्व (रूट)

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

उदाहरण

class TreeNode:
   def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

class Solution:
   def solve(self, root, a, b):
      if not root:
         return -1
      if root.val in (a, b):
         return root.val
      left = self.solve(root.left, a, b)
      right = self.solve(root.right, a, b)
      if -1 not in (left, right):
         return root.val
      return left if left != -1 else right
ob = Solution()
root = TreeNode(3)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root, 6, 2))

इनपुट

root = TreeNode(3)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
6, 2

आउटपुट

4