पायथन में न्यूनतम-अधिकतम गेम ट्री भरने का कार्यक्रम

मान लीजिए कि हमारे पास एक द्विआधारी पेड़ है जो दो खिलाड़ियों के खेल की स्थिति का प्रतिनिधित्व करता है। प्रत्येक आंतरिक नोड 0 से भरा होता है और पत्तियां मान अंतिम स्कोर का प्रतिनिधित्व करती हैं। खिलाड़ी 1 अंतिम स्कोर को अधिकतम करना चाहता है जबकि खिलाड़ी 2 अंतिम स्कोर को कम करना चाहता है। खिलाड़ी 1 हमेशा सम स्तरों पर नोड्स पर चलता है और खिलाड़ी 2 हमेशा विषम स्तरों पर चलता है। हमें बाइनरी ट्री को परिणामी स्कोर के साथ भरना होगा, यह मानते हुए कि दोनों खिलाड़ी बेहतर तरीके से खेलते हैं।

तो, अगर इनपुट पसंद है

तो आउटपुट होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फंक्शन हेल्पर () को परिभाषित करें। यह जड़ लेगा, h, currentHeight
• यदि जड़ खाली है, तो
  • वापसी
• सहायक (रूट के बाएँ, h, currentHeight + 1)
• सहायक (रूट का अधिकार, h, currentHeight + 1)
• यदि वर्तमानऊंचाई <एच, तो
  • यदि करंटहाइट सम है, तो
    • यदि रूट का बायां और रूट का दायां अशक्त नहीं है, तो
      • रूट का मान:=रूट के बाईं ओर का अधिकतम मान, रूट के दाईं ओर का मान
    • अन्यथा जब रूट का बायां भाग रिक्त न हो, तो
      • रूट का मान:=रूट के बाईं ओर का मान
    • अन्यथा जब मूल का अधिकार रिक्त नहीं है, तब
      • मूल का मान :=मूल के अधिकार का मान
  • अन्यथा,
    • यदि रूट का बायां और रूट का दायां अशक्त नहीं है, तो
      • रूट का मान:=रूट के बाईं ओर का मान, रूट के दाईं ओर का मान
    • अन्यथा जब रूट का बायां भाग रिक्त न हो, तो
      • रूट का मान:=रूट के बाईं ओर का मान
    • अन्यथा जब मूल का अधिकार रिक्त नहीं है, तब
      • मूल का मान :=मूल के अधिकार का मान
• फ़ंक्शन ऊंचाई () को परिभाषित करें। यह जड़ लेगा
• यदि रूट रिक्त है, तो
  • वापसी 0
• रिटर्न 1 + (अधिकतम ऊंचाई (रूट के बाएं), ऊंचाई (रूट के दाएं))
• मुख्य विधि से, निम्न कार्य करें -
• h :=ऊंचाई (रूट)
• सहायक(रूट, एच, 0)
• रिटर्न रूट

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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,