बाइनरी ट्री को रंगने की संभावना जांचने का पायथन प्रोग्राम जहां कोई आसन्न नोड्स समान रंग के न हों

मान लीजिए हमारे पास एक बाइनरी ट्री है जहां प्रत्येक नोड का मान उसका रंग दर्शाता है। एक ट्री में अधिकतम 2 रंग होते हैं। हमें जांचना है कि क्या नोड्स के रंगों को किसी भी संख्या में स्वैप करके ऐसा करना संभव है कि कोई दो जुड़े हुए नोड्स का रंग समान न हो।

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

तो आउटपुट True होगा क्योंकि हम प्राप्त कर सकते हैं:

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

• colors := एक खाली मैप
• prop := एक खाली मैप
• एक फ़ंक्शन dfs() परिभाषित करें। यह node और flag लेगा
• यदि node नल है, तो
  • लौटें
• colors[node का मान] := colors[node का मान] + 1
• prop[flag] := prop[flag] + 1
• dfs(node का बायाँ, flag का व्युत्क्रम)
• dfs(node का दायाँ, flag का व्युत्क्रम)
• मुख्य विधि से निम्न करें:
• dfs(root, सत्य)
• सत्य लौटाएं जब colors और prop में सभी तत्व समान हों, अन्यथा असत्य

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

उदाहरण

from collections import defaultdict
class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root):
        colors = defaultdict(int)
        prop = defaultdict(int)
        def dfs(node, flag=True):
            if not node:
                return
            colors[node.val] += 1
            prop[flag] += 1
            dfs(node.left, not flag)
            dfs(node.right, not flag)
        dfs(root)
        return set(colors.values()) == set(prop.values())

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.right.left = TreeNode(1)
root.right.right = TreeNode(1)
root.right.left.right = TreeNode(1)
print(ob.solve(root))

इनपुट

root = TreeNode(2)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.right.left = TreeNode(1)
root.right.right = TreeNode(1)
root.right.left.right = TreeNode(1)

आउटपुट

True