পাইথনে বাইনারি ট্রির পথ থেকে বने সংখ্যাগুলোর যোগফল বের করার প্রোগ্রাম

ধরুন একটি বাইনারি ট্রি আছে যেখানে প্রতিটি নোডে ০ থেকে ৯ পর্যন্ত একটি অঙ্ক রয়েছে। রুট থেকে পাতা নোড পর্যন্ত প্রতিটি পথ একটি সংখ্যা গঠন করে। আমাদের সব পথের সংখ্যাগুলোর যোগফল বের করতে হবে।

ইনপুট যদি নিচের মতো হয়:

তবে আউটপুট হবে ৯১৩ (৪৬ + ৪৩২ + ৪৩৫)।

সমাধানের ধাপগুলো:

solve() ফাংশন ডিফাইন করুন যা root এবং একটি স্ট্রিং গ্রহণ করে।
যদি নোড পাতা হয় (বাম ও ডান নেই), তবে স্ট্রিং+নোডের মান কনভার্ট করে রিটার্ন করুন।
total = 0।
বাম চাইল্ড থাকলে রিকার্সিভ কল করে যোগ করুন।
ডান চাইল্ড থাকলে রিকার্সিভ কল করে যোগ করুন।
total রিটার্ন করুন।

উদাহরণ

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, string=""):
        if root and not root.left and not root.right:
            return int(string + str(root.val))
        total = 0
        if root.left:
            total += int(self.solve(root.left, string + str(root.val)))
        if root.right:
            total += int(self.solve(root.right, string + str(root.val)))
        return total

ob = Solution()
root = TreeNode(4)
root.left = TreeNode(6)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(5)
print(ob.solve(root))

ইনপুট

root = TreeNode(4)
root.left = TreeNode(6)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(5)