Chương trình kiểm tra chuỗi inorder của cây có phải palindrome không bằng Python

Cho cây nhị phân mỗi nút chứa chữ số 0-9. Kiểm tra xem duyệt inorder của cây có phải palindrome hay không.

Ví dụ: inorder là [2, 6, 10, 6, 2] → True.

Quy trình giải quyết

1. Nếu gốc rỗng, trả về True.
2. Duyệt inorder không dùng đệ quy (dùng stack): đẩy nút và đi trái, sau đó pop, thêm giá trị, đi phải.
3. Kiểm tra danh sách inorder có bằng danh sách đảo ngược của nó hay không.

Ví dụ mã nguồn

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

Đầu vào

root = TreeNode(6) root.left = TreeNode(2) root.right = TreeNode(6) root.right.left = TreeNode(10) root.right.right = TreeNode(2)

Đầu ra

True