अजगर में एक बाइनरी ट्री में एकमात्र बच्चे की संख्या खोजने का कार्यक्रम

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें उन नोड्स की संख्या ज्ञात करनी है जो एकमात्र बच्चे हैं। जैसा कि हम जानते हैं कि एक नोड x को एकमात्र चाइल्ड नोड कहा जाता है, जब उसके माता-पिता के पास ठीक एक बच्चा होता है जो कि x होता है।

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

तो आउटपुट 2 होगा क्योंकि 8 और 6 इकलौते बच्चे हैं।

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

यदि रूट रिक्त है, तो
- वापसी 0
d :=एक डबल एंडेड कतार
d के अंत में रूट डालें
गिनती :=0
जबकि d खाली नहीं है, करें
- वर्तमान:=d का बायां तत्व और बायां तत्व हटाएं
- यदि धारा का बायां भाग शून्य नहीं है, तो
  - करंट के बाएँ को d में डालें
  - यदि धारा का अधिकार शून्य है, तो
    - गिनती :=गिनती + 1
  - यदि धारा का अधिकार शून्य नहीं है, तो
    - करंट का दायां d में डालें
    - यदि धारा का बायां भाग शून्य है, तो
      - गिनती :=गिनती + 1
वापसी की संख्या

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

उदाहरण कोड

from collections import deque

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      if not root:
         return 0
      d = deque()
      d.append(root)
      count = 0
      while d:
         current = d.popleft()
         if current.left:
            d.append(current.left)
            if not current.right:
               count += 1
            if current.right:
               d.append(current.right)
               if not current.left:
                  count += 1
         return count

ob = Solution()
root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.right = TreeNode(8)
root.right.right = TreeNode(6)
print(ob.solve(root))

इनपुट

root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.right = TreeNode(8)
root.right.right = TreeNode(6)