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

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें किन्हीं दो नोड्स के बीच किसी भी पथ का अधिकतम योग ज्ञात करना है।

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

तब आउटपुट 62 होगा क्योंकि नोड [12,13,14,16,7] हैं।

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

एक फ़ंक्शन को परिभाषित करें utils() । यह जड़ लेगा
अगर रूट अशक्त है, तो
- वापसी 0
l :=utils (रूट के बाएँ)
r :=utils(रूट के दायें)
max_single:=अधिकतम (अधिकतम l और r) + रूट का मान) और रूट का मान
max_top :=max_single का अधिकतम और l + r + रूट का मान
रेस :=अधिकतम रेस और मैक्स_टॉप
वापसी max_single
मुख्य विधि से, निम्न कार्य करें -
अगर रूट शून्य है, तो
- वापसी 0
रेस:=इन्फिनिटी
बर्तन (रूट)
रिटर्न रेस

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

उदाहरण

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None
class Solution:
   def solve(self, root):
      if root is None:
         return 0
      self.res = float("-inf")
      self.utils(root)
      return self.res
   def utils(self, root):
      if root is None:
         return 0
      l = self.utils(root.left)
      r = self.utils(root.right)
      max_single = max(max(l, r) + root.val, root.val)
      max_top = max(max_single, l + r + root.val)
      self.res = max(self.res, max_top)
      return max_single
ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

इनपुट

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)