মান ল করুন একটি বাইনারি ট্রি, আমাদের নোড ভ্যালুগুলোর সর্বোচ্চ যোগফল খুঁজে বের করতে হবে যাতে কোনো দুটি ভ্যালু এডজেসেন্ট প্যারেন্ট-চাইল্ড নয়।
যদি ইনপুট হয়:
তবে আউটপুট হবে ১৭ কারণ ১০, ৪, ৩ একে অপরের সাথে এডজেসেন্ট নয়।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- একটি f() ফাংশন সংজ্ঞায়িত করুন। এটি node গ্রহণ করবে।
- যদি node null হয়, (0, 0) ফেরত দিন।
- (a, b) := f(node.left), (c, d) := f(node.right)
- একটি পেয়ার ফেরত দিন: (max(node.val + b + d, a + c), a + c)
- মূল মেথড থেকে f(root) কল করে এর প্রথম মান ফেরত দিন।
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right def f(node): if not node: return 0, 0 a, b = f(node.left) c, d = f(node.right) return max(node.val + b + d, a + c), a + c class Solution: def solve(self, root): return f(root)[0] ob = Solution() root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(10) root.left.left = TreeNode(4) root.left.right = TreeNode(3) print(ob.solve(root))
ইনপুট
root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(10) root.left.left = TreeNode(4) root.left.right = TreeNode(3)
আউটপুট
17
