Chương trình duyệt cây nhị phân theo cấp độ xen kẽ trong Python

Cho cây nhị phân, duyệt theo cấp độ nhưng xen kẽ chiều: cấp chẵn trái→phải, cấp lẻ phải→trái (Zigzag Level Order Traversal).

Ví dụ: cây như hình → kết quả [5, -10, 4, -2, -7, 15].

Giải thuật (Hai stack)

1. Nếu root là None: trả về [].
2. Khởi tạo 2 stack: s1 = [root] (cấp chẵn), (cấp lẻ), res = [].
3. Khi hoặc không rỗng:
   • Xử lý (trái→phải): pop từ , thêm giá trị vào res, push con trái rồi con phải vào .
   • Xử lý (phải→trái): pop từ , thêm giá trị vào res, push con phải rồi con trái vào .
4. Trả về res.

Ví dụ minh họa

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]

Đầu vào

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)

Đầu ra

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