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

मान लीजिए कि हमारे पास एक बाइनरी ट्री है, हमें सबसे लगातार सबट्री योग खोजना होगा। एक नोड का सबट्री योग वास्तव में एक नोड के अंतर्गत सभी मानों का योग है, जिसमें स्वयं नोड भी शामिल है।

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

तो आउटपुट 3 होगा क्योंकि यह दो बार होता है - एक बार बाएं पत्ते के रूप में, और एक बार 3 - 6 + 6 के योग के रूप में।

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

गिनती :=एक खाली नक्शा
एक फ़ंक्शन को परिभाषित करें getSum() । यह नोड लेगा
यदि नोड शून्य है, तो
- वापसी 0
mySum :=getSum (नोड के बाएं) + getSum (नोड के दाएं) + नोड का मान
गिनती[mySum] :=count[mySum] + 1
माईसम लौटाएं
मुख्य विधि से निम्न कार्य करें
getSum(रूट)

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

उदाहरण

from collections import defaultdict
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      count = defaultdict(int)
      def getSum(node):
         if not node:
            return 0
         mySum = getSum(node.left) + getSum(node.right) + node.val
         count[mySum] += 1
         return mySum
      getSum(root)
      return max(count, key=count.get)
ob = Solution()
root = TreeNode(-6)
root.left = TreeNode(3)
root.right = TreeNode(6) print(ob.solve(root))

इनपुट

root = TreeNode(-6)
root.left = TreeNode(3)
root.right = TreeNode(6)