โปรแกรมเติมค่า Min-max game tree ใน Python

สมมติว่ามีต้นไม้แบบทวิภาคแทนสถานะเกม 2 คน โหนดภายในเติม 0 ใบไม้คือคะแนนจบเกม ผู้เล่น 1 ต้องการเพิ่มคะแนน (max) ผู้เล่น 2 ต้องการลดคะแนน (min) ผู้เล่น 1 เล่นที่ระดับคู่ ผู้เล่น 2 เล่นที่ระดับคี่ ต้องเติมค่าต้นไม้สมมติทั้งคู่เล่นอย่างเหมาะสม

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

1. ฟังก์ชัน helper(root, h, currentHeight):
   • ถ้า root ว่าง คืน
   • เรียกซ้ำซ้ายและขวา ก่อน (post-order)
   • ถ้า currentHeight < h:
     • ถ้าระดับคู่ (ผู้เล่น 1): root.val = max(left.val, right.val)
     • ถ้าระดับคี่ (ผู้เล่น 2): root.val = min(left.val, right.val)
     • จัดการกรณีมีลูกเพียงข้างเดียว
2. ฟังก์ชัน height(root) หาความสูงต้นไม้
3. จากเมธอดหลัก: h = height(root), เรียก helper(root, h, 0), คืน root

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

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))

อินพุต

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)

เอาต์พุต

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