โปรแกรมนับโหนดลูกเพียงลูกในต้นไม้แบบทวิภาคด้วย Python

สมมติว่ามีต้นไม้แบบทวิภาค (binary tree) ต้องการหาจำนวนโหนดที่เป็น "ลูกเพียงลูก" (only child) ซึ่งหมายถึงโหนดที่พาเรนต์มีลูกเพียงตัวเดียวเท่านั้น

ตัวอย่าง: โครงสร้างต้นไม้ที่มีโหนด 8 และ 6 เป็นลูกเพียงลูก ผลลัพธ์คือ 2

ขั้นตอนการแก้ปัญหา

1. ถ้า root เป็น null คืนค่า 0
2. ใช้คิวแบบสองหัว (deque) สำหรับ BFS
3. นำ root เข้าคิว, ตั้ง count = 0
4. วนลูป بينماคิวไม่ว่าง:
   • ดึงโหนด current จากด้านซ้าย
   • ถ้ามีลูกซ้าย:
     • นำลูกซ้ายเข้าคิว
     • ถ้าไม่มีลูกขวา เพิ่ม count
   • ถ้ามีลูกขวา:
     • นำลูกขวาเข้าคิว
     • ถ้าไม่มีลูกซ้าย เพิ่ม count
5. คืนค่า 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