Chương trình điền cây Min-Max game tree trong Python

Mô tả bài toán

Cho cây nhị phân biểu diễn trạng thái trò chơi 2 người. Các nút nội bộ ban đầu giá trị 0, nút lá là điểm cuối. Người chơi 1 (cấp độ chẵn) muốn tối đa hóa điểm, người chơi 2 (cấp độ lẻ) muốn tối thiểu hóa. Điền giá trị cho các nút nội bộ giả định cả hai chơi tối ưu.

Ví dụ: cây đầu vào (hình) → cây đầu ra (hình) sau khi điền giá trị Min-Max.

Giải thuật (Duyệt hậu tự - Postorder)

1. Định nghĩa hàm helper(root, h, currentHeight):
   • Nếu root rỗng: trả về.
   • Gọi đệ quy cho con trái và con phải với currentHeight+1.
   • Nếu currentHeight < h (không phải lá):
     • Nếu currentHeight chẵn (người chơi 1): gán giá trị lớn nhất của hai con (nếu cả hai tồn tại), hoặc giá trị con duy nhất.
     • Nếu lẻ (người chơi 2): gán giá trị nhỏ nhất của hai con (nếu cả hai tồn tại), hoặc giá trị con duy nhất.
2. Định nghĩa hàm height(root) tính chiều cao cây.
3. Từ hàm chính: h = height(root), gọi helper(root, h, 0), trả về root.

Ví dụ mã Python

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right

class Solution:
    def helper(self, root, h, currentHeight):
        if not root:
            return
        self.helper(root.left, h, currentHeight + 1)
        self.helper(root.right, h, currentHeight + 1)
        if currentHeight < h:
            if currentHeight % 2 == 0:
                if root.left and root.right:
                    root.val = max(root.left.val, root.right.val)
                elif root.left:
                    root.val = root.left.val
                elif root.right:
                    root.val = root.right.val
            else:
                if root.left and root.right:
                    root.val = min(root.left.val, root.right.val)
                elif root.left:
                    root.val = root.left.val
                elif root.right:
                    root.val = root.right.val

    def height(self, root):
        if not root:
            return 0
        return 1 + max(self.height(root.left), self.height(root.right))

    def solve(self, root):
        h = self.height(root)
        self.helper(root, h, 0)
        return root

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.val, end=', ')
        print_tree(root.right)

ob = Solution()
root = TreeNode(0)
root.left = TreeNode(3)
root.right = TreeNode(0)
root.right.left = TreeNode(0)
root.right.right = TreeNode(0)
root.right.left.left = TreeNode(-3)
root.right.right.right = TreeNode(4)
print_tree(ob.solve(root))

Đầu vào

root = TreeNode(0) root.left = TreeNode(3) root.right = TreeNode(0) root.right.left = TreeNode(0) root.right.right = TreeNode(0) root.right.left.left = TreeNode(-3) root.right.right.right = TreeNode(4)

Đầu ra

3, 3, -3, -3, -3, 4, 4,