पायथन में एक बाइनरी ट्री की जड़ से पत्ती तक सबसे लंबे योग पथ का योग खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी ट्री है, हमें रूट से लीफ नोड तक के सबसे लंबे पथ का योग ज्ञात करना है। यदि दो समान लंबे पथ हैं, तो पथ को अधिक राशि के साथ लौटाएं।

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

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

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

फ़ंक्शन rec() को परिभाषित करें। यह कठिन लगेगा
अगर कर्व शून्य है, तो
- वापसी(0, 0)
बड़ा:=अधिकतम रिक (कर के बाएँ), rec (कर्र का दाएँ)
एक जोड़ी लौटाएं (बड़ा [0] + 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):
      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)