यह जांचने के लिए कार्यक्रम कि क्या हम एक पेड़ को रंग सकते हैं जहां किसी भी आसन्न नोड्स का रंग समान नहीं है या नहीं

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

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

तो आउटपुट सही होगा जैसा कि हम प्राप्त कर सकते हैं

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

रंग :=एक खाली नक्शा
प्रोप:=एक खाली नक्शा
एक फ़ंक्शन को परिभाषित करें dfs() । यह नोड, और ध्वज लेगा
यदि नोड शून्य है, तो
- वापसी
रंग [नोड का मान] :=रंग [नोड का मान] + 1
प्रोप [ध्वज]:=सहारा [ध्वज] + 1
dfs (नोड के बाईं ओर, झंडे का उलटा)
dfs (नोड का दायां, ध्वज का उलटा)
मुख्य विधि से निम्न कार्य करें:
dfs(रूट, ट्रू)
जब रंग और प्रोप में सभी तत्व समान हों, अन्यथा गलत हो, तो सही लौटें

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

उदाहरण

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