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

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

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

तो रूट से आउटपुट 29 होगा, अगर हम 5-<9-<7-<8 पथ का अनुसरण करते हैं तो यह जोड़ के बाद 29 हो जाएगा।

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

फंक्शन वॉक () को परिभाषित करें। यह नोड लेगा, एस
यदि नोड शून्य है, तो
- max_sum :=max_sum और s का अधिकतम
- वापसी
s :=s + नोड का डेटा
वॉक (नोड के बाएं, एस)
वॉक (नोड के दाएं, एस)
मुख्य विधि से निम्न कार्य करें-
max_sum :=0
वॉक (रूट, 0)
वापसी max_sum

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

उदाहरण

from collections import defaultdict
   class TreeNode:
      def __init__(self, data, left = None, right = None):
         self.data = data
         self.left = left
         self.right = right
   class Solution:
      def walk(self, node, s):
         if not node:
            self.max_sum = max(self.max_sum, s)
         return
      s += node.data
      self.walk(node.left, s)
      self.walk(node.right, s)
   def solve(self, root):
      self.max_sum = 0
      self.walk(root, 0)
   return self.max_sum
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

इनपुट

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)