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

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

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সাহায্যকারী() সংজ্ঞায়িত করুন। এটি রুট, h, currentHeight
নেবে
• যদি রুট খালি থাকে, তাহলে
  • প্রত্যাবর্তন
• সহায়ক (মূলের বামে, h, বর্তমান উচ্চতা + 1)
• সহায়ক (মূলের ডানদিকে, h, বর্তমান উচ্চতা + 1)
• যদি বর্তমান উচ্চতা
• যদি বর্তমান উচ্চতা সমান হয়, তাহলে
  • মূলের বাম এবং রুটের ডানদিকে যদি শূন্য না হয়, তাহলে
    • মূলের মান :=রুটের বাঁদিকের সর্বোচ্চ, রুটের ডানের মান
  • অন্যথায় যখন রুটের বাম অংশ শূন্য না হয়, তখন
    • মূলের মান :=মূলের বাম মান
  • অন্যথায় যখন রুটের ডানদিকে শূন্য হয় না, তখন
    • মূলের মান :=মূলের অধিকারের মান
• অন্যথায়,
  • মূলের বাম এবং রুটের ডানদিকে যদি শূন্য না হয়, তাহলে
    • মূলের মান :=মূলের বামে ন্যূনতম মান, মূলের ডানের মান
  • অন্যথায় যখন রুটের বাম অংশ শূন্য না হয়, তখন
    • মূলের মান :=মূলের বাম মান
  • অন্যথায় যখন রুটের ডানদিকে শূন্য হয় না, তখন
    • মূলের মান :=মূলের অধিকারের মান

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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,