আমরা পাইথনে গাছটিকে দুটি গাছে কত উপায়ে ভাগ করতে পারি তা গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ট্রি আছে যেখানে মান 0, 1 এবং 2 রয়েছে। রুটে কমপক্ষে একটি 0 নোড এবং একটি 1 নোড রয়েছে। এখন ধরুন একটি অপারেশন আছে যেখানে আমরা গাছের একটি প্রান্ত মুছে ফেলি এবং গাছটি দুটি ভিন্ন গাছে পরিণত হয়। আমাদের একটি প্রান্ত মুছে ফেলার উপায় খুঁজে বের করতে হবে যাতে দুটি গাছের কোনোটিতেই 0 নোড এবং একটি 1 নোড থাকে না৷

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

তাহলে আউটপুট হবে 1 কারণ আমরা শুধুমাত্র 0 থেকে 2 প্রান্ত মুছে ফেলতে পারি।

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

গণনা :=[0, 0, 0]
একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড গ্রহণ করবে
যদি নোড নাল না হয়, তাহলে
- প্রি :=গণনা
- dfs(নোডের বামে)
- dfs(নোডের ডানদিকে)
- গণনা[নোডের মান] :=গণনা[নোডের মান] + 1
- node.count :=i 0 এবং 1 এর জন্য (count[i] - pre[i]) এর একটি তালিকা
একটি ফাংশন dfs2() সংজ্ঞায়িত করুন। এটি নোড, par
যদি নোড নাল না হয়, তাহলে
- যদি par শূন্য না হয়, তাহলে
  - (a0, a1) :=নোডের সংখ্যা
  - (b0, b1) :=(গণনা[0] - a0, গণনা[1] - a1)
  - যদি (a0 0 এর সমান বা a1 0 এর সমান) এবং (b0 0 বা b1 0 এর সমান), তাহলে
    - উত্তর :=উত্তর + ১
- dfs2 (নোডের বামে, নোড)
- dfs2 (নোডের ডানদিকে, নোড)
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
dfs(root)
উত্তর :=0
dfs2(root)
উত্তর ফেরত দিন

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

উদাহরণ

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):
      count = [0, 0, 0]
   def dfs(node):
      if node:
         pre = count[:]
         dfs(node.left)
         dfs(node.right)
         count[node.val] += 1
         node.count = [count[i] - pre[i] for i in range(2)]
   dfs(root)
   def dfs2(node, par=None):
      if node:
         if par is not None:
            a0, a1 = node.count
            b0, b1 = count[0] - a0, count[1] - a1
            if (a0 == 0 or a1 == 0) and (b0 == 0 or b1 == 0):
               self.ans += 1
         dfs2(node.left, node)
         dfs2(node.right, node)
   self.ans = 0
   dfs2(root)
   return self.ans
ob = Solution()
root = TreeNode(0)
root.left = TreeNode(0)
root.right = TreeNode(2)
root.right.left = TreeNode(1)
root.right.right = TreeNode(1)
print(ob.solve(root))

ইনপুট

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