โปรแกรมตรวจสอบว่าต้นไม้ไบนารีเป็นต้นไม้สมบูรณ์หรือไม่ใน Python

สมมติว่ามีต้นไม้ไบนารี เราต้องตรวจสอบว่ามันเป็นต้นไม้ไบนารีสมบูรณ์ (complete binary tree) หรือไม่ ต้นไม้สมบูรณ์คือทุกระดับเต็มไปด้วยโหนด ยกเว้นระดับสุดท้าย และโหนดในระดับสุดท้ายชิดซ้ายสุด

เช่น ถ้าอินพุตเป็นต้นไม้ดังภาพ ผลลัพธ์จะเป็น True

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

• q := double-ended queue
• ใส่ root เข้า q
• flag := False
• while q ไม่ว่าง
  • temp := ดึงจากซ้ายของ q
  • ถ้า temp เป็น null flag := True
  • ถ้า flag เป็น True และ temp ไม่ใช่ null คืนค่า False
  • มิฉะนั้น ใส่ left และ right ของ temp เข้า q
• คืนค่า True

ตัวอย่างโค้ด

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

อินพุต

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

เอาต์พุต

True