Binary Tree — BFS (ลุยเป็นชั้น)

หมวดที่แล้วเราใช้ DFS ลุยดิ่งลงกิ่งเดียวให้สุดก่อน หมวดนี้เราจะเจอวิธี traverse ต้นไม้อีกแบบที่ตรงข้ามกันเลย คือไล่ทีละ level จากบนลงล่าง ซ้ายไปขวา เรียกว่า BFS มันเหมาะกับโจทย์ที่ถามอะไรที่เป็น "level" เช่น ค่าของแต่ละ level หรือ node ขวาสุดของแต่ละ level

BFS / level-order คืออะไร

BFS ย่อมาจาก Breadth-First Search แปลว่า "ค้นแบบกวาดกว้างก่อน" บนต้นไม้เรามักเรียกอีกชื่อว่า level-order traversal คือ traverse ครบทั้ง level หนึ่งก่อน แล้วค่อยลง level ถัดไป ลองนึกภาพต้นไม้นี้: เราจะแตะ 3 ก่อน (level 1) แล้วแตะ 9, 20 (level 2) แล้วค่อย 15, 7 (level 3)

          3          <- ชั้น 1: [3]
         / \
        9   20         <- ชั้น 2: [9, 20]
           /  \
          15   7       <- ชั้น 3: [15, 7]

# ลำดับที่ BFS แตะ node: 3, 9, 20, 15, 7 (บนลงล่าง ซ้ายไปขวา)

เครื่องมือหัวใจของ BFS คือ queue (คิว) — โครงสร้างแบบ "เข้าก่อนออกก่อน" (FIFO) เราสร้าง queue ด้วย collections.deque (คิวสองหัว) ของ Python ซึ่ง popleft() (เอาตัวหน้าออก) เร็ว O(1) ต่างจาก list ธรรมดาที่ pop(0) ช้า O(n) ไอเดียคือ: enqueue root ใส่ queue แล้ว loop (วน) pop ออกทีละตัว พอ pop node ไหนออกมาก็ append (ต่อท้าย) left child และ right child ของมันเข้า queue loop แบบนี้ node จะทยอยออกมาเรียงตาม level พอดี

from collections import deque

# template BFS วนทีละชั้น ใช้ได้แทบทุกโจทย์ level-order
def level_order(root):
    if root is None:
        return
    queue = deque([root])          # เริ่มด้วย root ในคิว
    while queue:
        size = len(queue)          # จำนวน node ของชั้นนี้ (จดไว้ก่อน!)
        for _ in range(size):      # วนให้ครบทั้งชั้น
            node = queue.popleft() # ดึงตัวหน้าออก O(1)
            # ... ทำอะไรกับ node ตรงนี้ ...
            if node.left:
                queue.append(node.left)   # โยนลูกซ้ายเข้าคิว
            if node.right:
                queue.append(node.right)  # โยนลูกขวาเข้าคิว
        # จบ for = จบหนึ่งชั้นพอดี