โปรแกรมเดินทางต้นไม้ไบนารีระดับต่อระดับสลับทิศทางใน Python

สมมติว่าเรามีต้นไม้ไบนารี เราต้องแสดงค่าของแต่ละระดับโดยสลับทิศทางไปมาระหว่างซ้าย-ขวา และขวา-ซ้าย (Zigzag Level Order Traversal)

ตัวอย่างเช่น หากอินพุตเป็นต้นไม้ดังรูป ผลลัพธ์จะเป็น [5, -10, 4, -2, -7, 15]

ขั้นตอนการแก้ปัญหา (Two Stacks)

1. หาก root เป็น null ให้คืนค่ารายการว่าง
2. s1 = [root] (stack สำหรับระดับปัจจุบัน), s2 = [] (stack สำหรับระดับถัดไป)
3. res = []
4. วนลูป while s1 หรือ s2 ไม่ว่าง:
   • ประมวลผล s1 (ซ้าย-ขวา):
     • pop จาก s1, เพิ่มค่าเข้า res
     • push ลูกซ้าย แล้วลูกขวา เข้า s2
   • ประมวลผล s2 (ขวา-ซ้าย):
     • pop จาก s2, เพิ่มค่าเข้า res
     • push ลูกขวา แล้วลูกซ้าย เข้า s1
5. คืนค่า res

ตัวอย่างโค้ด Python

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))  # Output: [5, -10, 4, -2, -7, 15]

อินพุต

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]