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

मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें रूट से लीफ नोड तक के सबसे लंबे पथ का योग ढूंढना है। यदि दो समान लंबे पथ हैं, तो बड़े योग वाले पथ को वापस करें।

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

तो आउटपुट 20 होगा।

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

एक फ़ंक्शन rec() परिभाषित करें। यह curr लेगा
यदि curr null है, तो
- (0, 0) वापस करें
bigger := rec(curr का बायाँ) , rec(curr का दायाँ) का अधिकतम
एक जोड़ी वापस करें (bigger[0] + 1, bigger[1] + curr का मान)
मुख्य विधि से निम्नलिखित करें −
ret := rec(root)
ret का 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):       def rec(curr):          if not curr:             return (0, 0)          bigger = max(rec(curr.left), rec(curr.right))          return (bigger[0] + 1, bigger[1] + curr.val)       return rec(root)[1] ob = Solution() root = TreeNode(2) 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))

इनपुट

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