पायथन में हम पेड़ को दो पेड़ों में कितने तरीकों से विभाजित कर सकते हैं, यह गिनने का कार्यक्रम

मान लीजिए कि हमारे पास 0, 1 और 2 मान वाले बाइनरी ट्री हैं। रूट में कम से कम एक 0 नोड और एक 1 नोड है। अब मान लीजिए कि एक ऑपरेशन है जहां हम पेड़ में एक किनारे को हटाते हैं और पेड़ दो अलग-अलग पेड़ बन जाते हैं। हमें एक किनारे को हटाने के कई तरीके खोजने होंगे जैसे कि दो पेड़ों में से किसी में भी 0 नोड और 1 नोड दोनों न हों।

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

तो आउटपुट 1 होगा क्योंकि हम केवल 0 से 2 किनारे को हटा सकते हैं।

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

गिनती:=[0, 0, 0]
एक फ़ंक्शन को परिभाषित करें dfs() । यह नोड लेगा
यदि नोड रिक्त नहीं है, तो
- पूर्व :=गणना
- dfs(नोड के बाएं)
- dfs(नोड के दाएं)
- गिनती[नोड का मान] :=गिनती[नोड का मान] + 1
- node.count :=i के लिए (गिनती[i] - पूर्व[i]) की एक सूची 0 और 1 है
एक फ़ंक्शन परिभाषित करें dfs2() । यह नोड ले जाएगा, बराबर
यदि नोड रिक्त नहीं है, तो
- यदि बराबर शून्य नहीं है, तो
  - (a0, a1) :=नोड की संख्या
  - (b0, b1) :=(गिनती[0] - a0, गिनती[1] - a1)
  - यदि (a0 0 के समान है या a1 0 के समान है) और (b0 0 के समान है या b1 0 के समान है), तो
    - उत्तर:=उत्तर + 1
- dfs2 (नोड के बाएं, नोड)
- dfs2 (नोड का दायां, नोड)
मुख्य विधि से, निम्न कार्य करें -
dfs(रूट)
उत्तर:=0
dfs2(रूट)
वापसी उत्तर

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

उदाहरण

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)