Python에서 Min-max 게임 트리를 채우는 프로그램

2인용 게임의 게임 상태를 나타내는 이진 트리가 있다고 가정합니다. 모든 내부 노드는 0으로 채워지고 잎 값은 최종 점수를 나타냅니다. 참가자 1은 최종 점수를 최대화하려고 하고 참가자 2는 최종 점수를 최소화하려고 합니다. 플레이어 1은 항상 짝수 레벨의 노드에서 이동하고 플레이어 2는 항상 홀수 레벨에서 이동합니다. 두 플레이어가 최적의 상태로 플레이한다는 가정 하에 결과 점수로 이진 트리를 채워야 합니다.

따라서 입력이 다음과 같으면

그러면 출력은

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• helper() 함수를 정의합니다. 이것은 root, h, currentHeight
를 취합니다.
• 루트가 비어 있으면
  • 반환
• 도우미(루트 왼쪽, h, currentHeight + 1)
• 도우미(루트의 오른쪽, h, currentHeight + 1)
• currentHeight
• currentHeight가 짝수이면
  • 루트의 왼쪽과 루트의 오른쪽이 null이 아니면
    • 루트 값 :=루트 왼쪽 값의 최대값, 루트 오른쪽 값
  • 그렇지 않으면 root의 왼쪽이 null이 아닌 경우
    • 루트 값 :=루트 왼쪽 값
  • 그렇지 않으면 루트의 오른쪽이 null이 아닌 경우
    • 루트 값 :=루트 오른쪽 값
• 그렇지 않으면
  • 루트의 왼쪽과 루트의 오른쪽이 null이 아니면
    • 루트 값 :=루트 왼쪽 값의 최소값, 루트 오른쪽 값
  • 그렇지 않으면 root의 왼쪽이 null이 아닌 경우
    • 루트 값 :=루트 왼쪽 값
  • 그렇지 않으면 루트의 오른쪽이 null이 아닌 경우
    • 루트 값 :=루트 오른쪽 값

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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,