পাইথনে বাইনারি ট্রি লেভেল-ওয়াইজ অল্টারনেটিং ট্রাভার্সাল প্রোগ্রাম

ধরা যাক একটি বাইনারি ট্রি আছে, আমাদের প্রতিটি লেভেলের মান বাম-থেকে-ডান এবং ডান-থেকে-বাম অল্টারনেট করে দেখাতে হবে।

উদাহরণ ট্রি হলে আউটপুট [5, -10, 4, -2, -7, 15]।

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

• যদি root null হয়, খালি তালিকা ফেরত দিন।
• s1 := [root], s2 := [], res := []
• যখন s1 বা s2 খালি নয়:
• যখন s1 খালি নয়: node = s1.pop(), node.left এবং node.right s2-এ পুশ করুন, node.val res-এ অ্যাপেন্ড করুন।
• যখন s2 খালি নয়: node = s2.pop(), node.right এবং node.left s1-এ পুশ করুন, node.val res-এ অ্যাপেন্ড করুন।
• res ফেরত দিন।

উদাহরণ কোড

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):
        if not root:
            return []
        s1 = [root]
        s2 = []
        res = []
        while s1 or s2:
            while s1:
                node = s1.pop()
                if node.left:
                    s2.append(node.left)
                if node.right:
                    s2.append(node.right)
                res.append(node.val)
            while s2:
                node = s2.pop()
                if node.right:
                    s1.append(node.right)
                if node.left:
                    s1.append(node.left)
                res.append(node.val)
        return res

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(-10)
root.left.left = TreeNode(-2)
root.right.left = TreeNode(-7)
root.right.right = TreeNode(15)
print(ob.solve(root))

ইনপুট

root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(-10) root.left.left = TreeNode(-2) root.right.left = TreeNode(-7) root.right.right = TreeNode(15)

আউটপুট

[5, -10, 4, -2, -7, 15]