পাইথনে বাইনারি ট্রিতে শুধু সন্তানের সংখ্যা বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি বাইনারি ট্রি আছে; আমাদের কাজ হল সেই নোডগুলোর সংখ্যা বের করা যারা only child (একমাত্র সন্তান)। আমরা জানি, একটি নোড x হল only child যখন এর প্যারেন্টের শুধুমাত্র একই সন্তান আছে অর্থাৎ x।

উদাহরণস্বরূপ, যদি ইনপুট ট্রিটি নিচের ছবির মতো হয়:

তবে আউটপুট হবে 2 কারণ ৮ এবং ৬ - এই দুটি নোড হল শুধু সন্তান।

• যদি root নাল হয়, তবে 0 রিটার্ন করুন।
• d := একটি ডাবল-এন্ডেড কিউ (deque)
• root কে d-র শেষে ঢুকান।
• count := 0
• d খালি না হওয়া পর্যন্ত লুপ চালান:
  • current := d-র বাম দিকের এলিমেন্ট নিন এবং সেটি মুছুন।
  • যদি current-র বাম সন্তান নাল না হয়, তবে:
    • বাম সন্তানকে d-তে ঢুকান।
    • যদি current-র ডান সন্তান নাল হয়, তবে count := count + 1।
  • যদি 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)

2