পাইথনে একটি বাইনারি গাছের সর্বাধিক ঘন ঘন সাবট্রি যোগফল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি গাছ আছে, আমাদের সবচেয়ে ঘন ঘন সাবট্রি যোগফল খুঁজে বের করতে হবে। একটি নোডের সাবট্রি সমষ্টি আসলে নোড সহ একটি নোডের অধীনে থাকা সমস্ত মানের সমষ্টি।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট 3 হবে কারণ এটি দুইবার হয় - একবার বাম পাতার মতো, এবং একবার 3 - 6 + 6 এর যোগফল হিসেবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

গণনা :=একটি খালি মানচিত্র
একটি ফাংশন getSum() সংজ্ঞায়িত করুন। এটি নোড গ্রহণ করবে
যদি নোড নাল হয়, তাহলে
- রিটার্ন 0
mySum :=getSum(নোডের বামে) + getSum(নোডের ডানদিকে) + নোডের মান
count[mySum] :=count[mySum] + 1
মাইসুম ফেরত দিন
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন
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)