পাইথনে বাইনারি ট্রিতে রুট থেকে লিফ পর্যন্ত যেকোনো পথের সর্বোচ্চ যোগফল খুঁজে বের করার প্রোগ্রাম

মনে করুন একটি বাইনারি ট্রি আছে। রুট নোড থেকে লিফ নোড পর্যন্ত যেকোনো পথের সর্বোচ্চ যোগফল খুঁজে বের করতে হবে।

ইনপুট ট্রির ছবি দেওয়া আছে, আউটপুট ২৯ (পথ: ৫-৯-৭-৮)۔

সমাধানের ধাপসমূহ

walk(node, s) ফাংশন সংজ্ঞায়িত করুন
- যদি node null হয়, max_sum = max(max_sum, s), ফেরত যান
- s += node.data
- walk(node.left, s), walk(node.right, s)
মূল মেথড: max_sum := 0, walk(root, 0), max_sum ফেরত দিন

উদাহরণ

from collections import defaultdict
class TreeNode:
    def __init__(self, data, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right

class Solution:
    def walk(self, node, s):
        if not node:
            self.max_sum = max(self.max_sum, s)
            return
        s += node.data
        self.walk(node.left, s)
        self.walk(node.right, s)
    def solve(self, root):
        self.max_sum = 0
        self.walk(root, 0)
        return self.max_sum

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

ইনপুট

root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8)