Chương trình điền cây trò chơi Min-max bằng Python

Giả sử chúng ta có một cây nhị phân biểu diễn trạng thái trò chơi của trò chơi hai người chơi. Mọi nút bên trong được điền bằng 0 và các giá trị của lá biểu thị điểm kết thúc. Người chơi 1 muốn tối đa hóa điểm số cuối cùng trong khi người chơi 2 muốn giảm thiểu điểm số cuối cùng. Người chơi 1 sẽ luôn di chuyển trên các nút ở cấp độ chẵn và người chơi 2 sẽ luôn thực hiện di chuyển ở cấp độ lẻ. Chúng ta phải điền vào cây nhị phân với kết quả điểm giả sử cả hai người chơi đều chơi tối ưu.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm trợ giúp (). Điều này sẽ có gốc, h, currentHeight
• nếu gốc trống, thì
  • trở lại
• trình trợ giúp (bên trái của thư mục gốc, h, currentHeight + 1)
• trình trợ giúp (quyền root, h, currentHeight + 1)
• if currentHeight
• nếu currentHeight là chẵn thì
  • nếu bên trái của thư mục gốc và bên phải của thư mục gốc không rỗng, thì
    • giá trị của gốc:=giá trị lớn nhất của bên trái của gốc, giá trị của bên phải của gốc
  • ngược lại, khi bên trái của thư mục gốc không rỗng, thì
    • giá trị của gốc:=giá trị của bên trái của gốc
  • ngược lại khi bên phải của thư mục gốc không rỗng, thì
    • value of root:=giá trị của quyền root
• nếu không,
  • nếu bên trái của thư mục gốc và bên phải của thư mục gốc không rỗng, thì
    • giá trị của gốc:=giá trị nhỏ nhất của giá trị bên trái của gốc, giá trị của bên phải của gốc
  • ngược lại, khi bên trái của thư mục gốc không rỗng, thì
    • giá trị của gốc:=giá trị của bên trái của gốc
  • ngược lại khi bên phải của thư mục gốc không rỗng, thì
    • value of root:=giá trị của quyền root

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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,