สมมติว่าเรามีต้นไม้ไบนารี เราต้องตรวจสอบว่านี่เป็นไบนารีทรีที่สมบูรณ์หรือไม่ ดังที่เราทราบในไบนารีทรีที่สมบูรณ์ ระดับต่างๆ จะเต็มไปด้วยโหนด ยกเว้นโหนดสุดท้ายและโหนดทั้งหมดในระดับสุดท้ายจะอยู่ซ้ายสุดเท่าที่จะทำได้
ดังนั้นหากอินพุตเป็นแบบ
แล้วผลลัพธ์จะเป็น True
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-
-
q :=คิวที่สิ้นสุดสองครั้ง
-
แทรกรูทที่ส่วนท้ายของ q
-
ธง :=เท็จ
-
ในขณะที่ q ไม่ว่างให้ทำ
-
temp :=องค์ประกอบหลังจากลบจากด้านซ้ายของ q
-
ถ้า temp เป็นโมฆะ
-
ธง :=จริง
-
-
มิฉะนั้นเมื่อตั้งค่าสถานะและอุณหภูมิไม่เป็นโมฆะ
-
คืนค่าเท็จ
-
-
มิฉะนั้น
-
แทรกด้านซ้ายของ temp ที่ส่วนท้ายของ q
-
แทรกด้านขวาของ 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
