โปรแกรมตรวจสอบลำดับ Inorder ของต้นไม้เป็นพาลินโดรมหรือไม่ใน Python

สมมติว่าเรามีต้นไม้ทวิภาคที่แต่ละโหนดมีตัวเลข 0-9 เราต้องตรวจสอบว่า inorder traversal ของมันเป็นพาลินโดรมหรือไม่

ตัวอย่าง: จากภาพ inorder คือ [2,6,10,6,2] เป็นพาลินโดรม ผลลัพธ์ True

ขั้นตอนการแก้ปัญหา

1. ถ้า root เป็น None: คืนค่า True
2. สร้างสแต็ก stack, curr = root, inorder = []
3. วนลูป while stack หรือ curr:
   • วนลูป while curr: ใส่ curr เข้า stack, curr = curr.left
   • node = stack.pop(), เพิ่ม node.val เข้า inorder
   • curr = node.right
4. คืนค่า inorder == inorder[::-1]

ตัวอย่างโค้ด 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 True
        stack = []
        curr = root
        inorder = []
        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            node = stack.pop()
            inorder.append(node.val)
            curr = node.right
        return inorder == inorder[::-1]

ob = Solution()
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)
print(ob.solve(root))  # Output: True

อินพุต / เอาต์พุต

Input: ต้นไม้ตามโค้ดตัวอย่าง

Output: True