পাইথনে বাইনারি ট্রিতে প্রতিটি ডায়াগোনাল পথের উপাদানগুলোর যোগফল খুঁজে বের করার প্রোগ্রাম

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

ইনপুট ট্রি এবং আউটপুট [27, 18, 3] এর ছবি দেওয়া আছে, কারণ ডায়াগোনালগুলো হল [12,15], [8,10], [3]।

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

• traverse() ফাংশন সংজ্ঞায়িত করুন যা node, numLeft, output নেয়
• যদি node null হয়, তবে
  • ফেরত যান
• যদি numLeft >= output-এর আকার, তবে
  • output-এর শেষে node.data যোগ করুন
• অন্যথায়,
  • output[numLeft] := output[numLeft] + node.data
• যদি node.left নন-নাল, তবে
  • traverse(node.left, numLeft+1, output)
• যদি node.right নন-নাল, তবে
  • traverse(node.right, numLeft, output)
• মূল মেথড থেকে:
  • output := নতুন তালিকা
  • traverse(root, 0, output)
  • output ফেরত দিন

উদাহরণ

class TreeNode:
    def __init__(self, data, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root):
        output = []
        def traverse(node, numLeft, output):
            if not node:
                return
            if numLeft >= len(output):
                output.append(node.data)
            else:
                output[numLeft] += node.data
            if node.left:
                traverse(node.left, numLeft+1, output)
            if node.right:
                traverse(node.right, numLeft, output)
        traverse(root, 0, output)
        return output

ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root))

ইনপুট

root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10)

আউটপুট

[27, 18, 3]