पायथन में बाइनरी ट्री में केवल बच्चे नोड्स की संख्या खोजने का प्रोग्राम

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

उदाहरण के लिए, यदि इनपुट निम्न ट्री है:

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

समाधान दृष्टिकोण

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

यदि रूट नल है, तो 0 लौटाएं
d := एक डबल-एंडेड क्यू
रूट को d के अंत में डालें
count := 0

जब तक d खाली नहीं है:

current := d का बायां तत्व लें और हटाएं
यदि current का बायां बच्चा नल नहीं है:
- current के बाएं बच्चे को d में डालें
- यदि current का दायां बच्चा नल है:
  - count := count + 1
- यदि current का दायां बच्चा नल नहीं है:
  - current के दाएं बच्चे को d में डालें
  - यदि current का बायां बच्चा नल है:
    - count := count + 1
count लौटाएं

उदाहरण कोड

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)