पायथन में बाइनरी ट्री कलरिंग गेम

मान लीजिए दो खिलाड़ी बाइनरी ट्री पर टर्न-बेस्ड गेम खेलते हैं। हमारे पास इस बाइनरी ट्री का रूट और ट्री में नोड्स की संख्या n है। यहां n विषम है, और प्रत्येक नोड का 1 से n तक एक विशिष्ट मान है। पहले, पहला खिलाड़ी 1 <= x <= n के साथ एक मान x नाम देता है, और दूसरा खिलाड़ी 1 <= y <= n के साथ एक मान y नाम देता है और वह एक शर्त रखता है, जैसे कि y != x। पहला खिलाड़ी मान x वाले नोड को लाल रंग से रंगता है, और दूसरा खिलाड़ी मान y वाले नोड को नीले रंग से रंगता है। उसके बाद, खिलाड़ी पहले खिलाड़ी से शुरू करके टर्न लेते हैं। प्रत्येक टर्न में, खिलाड़ी अपने रंग का एक नोड लेता है (खिलाड़ी 1 के लिए लाल, खिलाड़ी 2 के लिए नीला) और चुने गए नोड के अनकलर्ड नेबर को रंगता है (या तो बायां या दायां चाइल्ड, या लिए गए नोड का पैरेंट)। यदि और केवल यदि कोई खिलाड़ी इस तरह से ऐसा नोड नहीं ले सकता, तो उन्हें अपना टर्न पास करना होगा। यदि दोनों खिलाड़ी अपना टर्न पास करते हैं, तो गेम समाप्त हो जाएगा, और विजेता वह खिलाड़ी होगा जिसने अधिक नोड्स रंगा है।

मान लीजिए हम दूसरा खिलाड़ी हैं। यदि ऐसा y चुनना संभव है जिससे हम गेम जीतना सुनिश्चित करें, तो true लौटाएं। यदि यह संभव नहीं है, तो false लौटाएं।

इसलिए यदि ट्री इस तरह है -

और n 11 है और x 3 है, तो आउटपुट true होगा, क्योंकि दूसरा खिलाड़ी मान 2 वाले नोड को ले सकता है।

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

• solve() नामक एक मेथड परिभाषित करें, यह node, x, l और r लेगा, l और r प्रारंभ में false हैं, यह नीचे की तरह कार्य करेगा -

• यदि node मौजूद नहीं है, तो लौटें और बाहर निकलें

• यदि l true है, तो leftVal को 1 से बढ़ाएं, अन्यथा जब r true है, तो rightVal को 1 से बढ़ाएं

• यदि नोड मान x है, तो solve(node का बायां, x, true, false) कॉल करें और solve(node का दायां, x, false, true) कॉल करें

• अन्यथा solve(node का बायां, x, l, r) कॉल करें और solve(node का दायां, x, l, r) कॉल करें

• मुख्य मेथड इस तरह होगा -

• nodeToX := 0, leftVal := 0, rightVal := 0

• solve(root, x, false, false) कॉल करें

• nodeToX := n - leftVal - rightVal - 1

• temp := rightVal, nodeToX और leftVal का अधिकतम

• false लौटाएं यदि (nodeToX + leftVal + rightVal - (2*temp) >= 0), अन्यथा true

उदाहरण (पायथन)

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

class TreeNode:
    def __init__(self, data, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right

def insert(temp,data):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        self.nodeToX = 0
        self.leftVal = 0
        self.rightVal = 0
        self.solve(root,x)
        self.nodeToX = n - self.leftVal - self.rightVal - 1
        temp = max(self.rightVal,max(self.nodeToX,self.leftVal))
        return not (self.nodeToX + self.leftVal + self.rightVal - (2*temp)>=0)
    def solve(self,node,x,l= False,r = False):
        if not node:
            return
        if l:
            self.leftVal+=1
        elif r:
            self.rightVal+=1
        if node.data == x:
            self.solve(node.left,x,True,False)
            self.solve(node.right,x,False,True)
        else:
            self.solve(node.left,x,l,r)
            self.solve(node.right,x,l,r)

ob = Solution()
root = make_tree([1,2,3,4,5,6,7,8,9,10,11])
print(ob.btreeGameWinningMove(root, 11, 3))

इनपुट

[1,2,3,4,5,6,7,8,9,10,11] 11 3

आउटपुट

true