Chương trình đếm số nút là con duy nhất trong cây nhị phân bằng Python

Mô tả bài toán

Cho một cây nhị phân. Cần đếm số nút là "con duy nhất" (only child), tức nút mà cha của nó chỉ có đúng một con là chính nút đó.

Ví dụ: cây như hình (9 là gốc, con trái 7, con phải 10; 7 có con phải 8; 10 có con phải 6). Các nút con duy nhất là 8 và 6 → kết quả 2.

Giải thuật (BFS)

1. Nếu gốc rỗng, trả về 0.
2. Sử dụng hàng đợi double-ended queue d, đưa gốc vào.
3. Khởi tạo count = 0.
4. Khi hàng đợi không rỗng:
   • Lấy nút current từ đầu hàng đợi.
   • Nếu current.left tồn tại: đưa vào hàng đợi; nếu current.right không tồn tại → tăng count.
   • Nếu current.right tồn tại: đưa vào hàng đợi; nếu current.left không tồn tại → tăng count.
5. Trả về count.

Ví dụ mã Python

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))

Đầu vào

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

Đầu ra

2