पायथन में मिन-मैक्स गेम ट्री भरने का प्रोग्राम

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

उदाहरण के लिए, यदि इनपुट ट्री है:

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

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• एक फंक्शन helper() परिभाषित करें जो root, h, currentHeight लेता है
• यदि root खाली है, तो लौटें
• helper(root.left, h, currentHeight+1)
• helper(root.right, h, currentHeight+1)
• यदि currentHeight < h:
  • यदि currentHeight सम है (खिलाड़ी 1 की बारी):
    • यदि दोनों बच्चे मौजूद हैं: root.val = max(left.val, right.val)
    • अन्यथा यदि केवल बायां बच्चा: root.val = left.val
    • अन्यथा यदि केवल दायां बच्चा: root.val = right.val
  • अन्यथा (खिलाड़ी 2 की बारी):
    • यदि दोनों बच्चे मौजूद हैं: root.val = min(left.val, right.val)
    • अन्यथा यदि केवल बायां बच्चा: root.val = left.val
    • अन्यथा यदि केवल दायां बच्चा: root.val = right.val
• एक फंक्शन height() परिभाषित करें जो ट्री की ऊंचाई लौटाता है
• मुख्य मेथड से:
  • 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,