Chương trình kiểm tra cây nhị phân có phải cây hoàn chỉnh không trong Python

Cho cây nhị phân, kiểm tra xem có phải cây hoàn chỉnh (complete binary tree) không: các cấp độ đầy trừ cấp cuối, nút cuối cùng chững trái nhất.

Ví dụ

Cây đầu vào: (hình ảnh).
Đầu ra: True.

Thuật toán

1. Sử dụng hàng đợi (deque) duyệt theo chiều rộng (BFS).
2. Khởi tạo flag = False.
3. Khi hàng đợi không rỗng:
   • Lấy nút temp.
   • Nếu temp là None: flag = True.
   • Nếu flag và temp không None: trả về False.
   • Ngược lại: đẩy con trái và con phải vào hàng đợi.
4. Trả về True.

Mã nguồn 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):
        q = deque()
        q.append(root)
        flag = False
        while q:
            temp = q.popleft()
            if not temp:
                flag = True
            elif flag and temp:
                return False
            else:
                q.append(temp.left)
                q.append(temp.right)
        return True

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

Đầu vào / Đầu ra

Input: root = TreeNode(9) ...
Output: True