पायथन में बाइनरी ट्री के सबसे अधिक बार आने वाले सबट्री योग को खोजने का प्रोग्राम

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

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

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

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

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

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

उदाहरण

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)