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

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

इसलिए, यदि इनपुट इस तरह है

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

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

एक विधि solve() परिभाषित करें यह root और a, b लेगा
यदि root null है, तो
- -1 वापस करें
यदि root का मान या तो a या b है, तो
- root का मान वापस करें
left := solve(root का बायाँ, a, b)
right := solve(root का दायाँ, a, b)
यदि left या right, -1 नहीं है, तो
- root का मान वापस करें
left वापस करें यदि left, -1 के समान नहीं है अन्यथा right
मुख्य विधि से solve(root) कॉल करें

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

उदाहरण

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