মান ল করুন একটি বাইনারি ট্রি, আমাদের রুট থেকে লিফ নোড পর্যন্ত সবচেয়ে লম্বা পাথের যোগফল খুঁজে বের করতে হবে। যদি দুটি একই দৈর্ঘ্যের পাথ থাকে, বড় যোগফল वाली পাথ ফেরত দিন।
যদি ইনপুট হয়:
তবে আউটপুট হবে ২০।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- একটি rec() ফাংশন সংজ্ঞায়িত করুন। এটি curr গ্রহণ করবে।
- যদি curr null হয়, (0, 0) ফেরত দিন।
- bigger := max(rec(curr.left), rec(curr.right))
- (bigger[0] + 1, bigger[1] + curr.val) ফেরত দিন।
- মূল মেথড থেকে: ret := rec(root), ret[1] ফেরত দিন।
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def solve(self, root): def rec(curr): if not curr: return (0, 0) bigger = max(rec(curr.left), rec(curr.right)) return (bigger[0] + 1, bigger[1] + curr.val) return rec(root)[1] ob = Solution() root = TreeNode(2) root.left = TreeNode(10) root.right = TreeNode(4) root.right.left = TreeNode(8) root.right.right = TreeNode(2) root.right.left.left = TreeNode(6) print(ob.solve(root))
ইনপুট
root = TreeNode(2) root.left = TreeNode(10) root.right = TreeNode(4) root.right.left = TreeNode(8) root.right.right = TreeNode(2) root.right.left.left = TreeNode(6)
আউটপুট
20
