আমরা এমন একটি গাছকে রঙ করতে পারি কিনা তা পরীক্ষা করার জন্য প্রোগ্রাম যেখানে কোনও সংলগ্ন নোডের রঙ একই রকম নেই বা পাইথনে নেই

ধরুন আমাদের একটি বাইনারি ট্রি আছে যেখানে প্রতিটি নোডের মান তার রঙের প্রতিনিধিত্ব করে। একটি গাছে সর্বাধিক 2টি রঙ থাকে। আমাদের চেক করতে হবে যে নোডের রং যে কোনো সংখ্যক বার অদলবদল করা সম্ভব কিনা যাতে কোনো দুটি সংযুক্ত নোডের রঙ একই না হয়।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট True হবে যেমন আমরা পেতে পারি

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• রঙ :=একটি খালি মানচিত্র
• prop :=একটি খালি মানচিত্র
• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড এবং পতাকা গ্রহণ করবে
• যদি নোড নাল হয়, তাহলে
  • প্রত্যাবর্তন
• রঙ[নোডের মান] :=রং[নোডের মান] + 1
• প্রপ[ফ্ল্যাগ] :=প্রপ[ফ্ল্যাগ] + 1
• dfs (নোডের বাম, পতাকার বিপরীত)
• dfs (নোডের ডানদিকে, পতাকার বিপরীত)
• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
• dfs(root, true)
• সত্য প্রত্যাবর্তন করুন যখন রঙ এবং প্রপের সমস্ত উপাদান একই, অন্যথায় মিথ্যা

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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