মান ল করুন একটি বাইনারি ট্রি, আমাদের সবচেয়ে কমন সাবট্রি সম খুঁজে বের করতে হবে। একটি নোডের সাবট্রি সম আসলে সেই নোডের অধীনে থাকা সব মানগুলোর যোগফল, নিজের মান সহ।
যদি ইনপুট হয়:
তবে আউটপুট হবে ৩ কারণ এটি দুবার আসে — একবার বাম লিফ হিসেবে, আরেকবার 3 - 6 + 6 এর যোগফল হিসেবে।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- count := একটি খালি ম্যাপ
- একটি getSum() ফাংশন সংজ্ঞায়িত করুন। এটি node গ্রহণ করবে।
- যদি node null হয়, ০ ফেরত দিন।
- mySum := getSum(node.left) + getSum(node.right) + node.val
- count[mySum] := count[mySum] + 1
- mySum ফেরত দিন
- মূল মেথড থেকে: getSum(root) কল করুন, count-এ সর্বোচ্চ ফ্রিকোয়েন্সি থাকা key ফেরত দিন।
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
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)
আউটপুট
3
