পাইথনে মিন-ম্যাক্স গেম ট্রি পূরণ করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি বাইনারি ট্রি আছে যেটি দুই খেলোয়াড়ের গেম স্টেটকে প্রতিনিধিত্ব করে। প্রতিটি ইন্টারনাল নোড ০ দিয়ে ভরা আছে এবং লিফ নোডগুলোর মান গেমের চূড়ান্ত স্কোর। খেলোয়াড় ১ চূড়ান্ত স্কোর বড় করতে চায় আর খেলোয়াড় ২ ছোট করতে চায়। খেলোয়াড় ১ সবসময় কন লেভেলের নোডগুলতে মুভ দেবে আর খেলোয়াড় ২ বিজোড় লেভেলের নোডগুলতে। উভয় খেলোয়াড় ইনফিনিটলি অপ্টিমালি খেললে ট্রিটি কীভাবে পূরণ হবে সেটি বের করতে হবে।

উদাহরণস্বরূপ, যদি ইনপুট ট্রিটি নিচের ছবির মতো হয়:

তবে আউটপুট হবে নিচের ছবির মতো:

• একটি helper() ফাংশন ডিফাইন করুন যা root, h, currentHeight নেবে।
  • যদি root খালি হয়, তবে রিটার্ন করুন।
  • helper(root.left, h, currentHeight+1)
  • helper(root.right, h, currentHeight+1)
  • যদি currentHeight < h হয়, তবে:
    • যদি currentHeight জোড় হয় (খেলোয়াড় ১), তবে:
      • যদি দুটি চাইল্ডই নাল না হয়, তবে root.val = max(root.left.val, root.right.val)
      • অন্যথায় যদি বাম চাইল্ড নাল না হয়, তবে root.val = root.left.val
      • অন্যথায় যদি ডান চাইল্ড নাল না হয়, তবে root.val = root.right.val
    • অন্যথায় (খেলোয়াড় ২), তবে:
      • যদি দুটি চাইল্ডই নাল না হয়, তবে root.val = min(root.left.val, root.right.val)
      • অন্যথায় যদি বাম চাইল্ড নাল না হয়, তবে root.val = root.left.val
      • অন্যথায় যদি ডান চাইল্ড নাল না হয়, তবে root.val = root.right.val
• একটি height() ফাংশন ডিফাইন করুন যা root নেবে।
  • যদি root নাল হয়, তবে 0 রিটার্ন করুন।
  • 1 + max(height(root.left), height(root.right)) রিটার্ন করুন।
• মূল মেথড থেকে:
  • 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,