LeetCode 102 Level Order Traversal: เลือก queue, index หรือ DFS

โจทย์ให้ binary tree แล้วต้องคืนค่าของ node แยกเป็นรายการตามระดับจาก root ลงมาและซ้ายไปขวาครับ คำตอบธรรมชาติคือ BFS แต่ยังมีรายละเอียดว่า queue แบบใดและจะจัด boundary ของแต่ละ level อย่างไร

WHY: frontier คือ state หลัก

BFS เก็บ node ที่รอเยี่ยมใน queue เมื่อเริ่มรอบหนึ่ง ขนาด queue คือจำนวน node ของ level ปัจจุบัน เราจึง pop เท่านั้นแล้ว append ลูกสำหรับรอบถัดไป วิธีนี้ O(n) time และ O(w) memory โดย w คือความกว้างสูงสุดของต้นไม้

list.pop(0) ดูง่ายแต่เลื่อนสมาชิกทุกครั้งจนเสี่ยง O(n²) ใช้ collections.deque หรือ list ที่มี head index เพื่อให้การนำหน้าออกเป็น O(1) amortized

HOW: ทดสอบสามแนวคิดกับ tree เดียวกัน

import unittest
from collections import deque
from dataclasses import dataclass


@dataclass
class Node:
    value: int
    left: "Node | None" = None
    right: "Node | None" = None


def levels_deque(root):
    if root is None:
        return []
    queue, result = deque([root]), []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result


def levels_index(root):
    if root is None:
        return []
    queue, head, result = [root], 0, []
    while head < len(queue):
        end, level = len(queue), []
        while head < end:
            node = queue[head]
            head += 1
            level.append(node.value)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result


def levels_dfs(root):
    result = []
    def visit(node, depth):
        if node is None: return
        if depth == len(result): result.append([])
        result[depth].append(node.value)
        visit(node.left, depth + 1)
        visit(node.right, depth + 1)
    visit(root, 0)
    return result


class LevelTests(unittest.TestCase):
    def test_methods(self):
        tree = Node(3, Node(9), Node(20, Node(15), Node(7)))
        expected = [[3], [9, 20], [15, 7]]
        for function in (levels_deque, levels_index, levels_dfs):
            self.assertEqual(function(tree), expected)
            self.assertEqual(function(None), [])


if __name__ == "__main__":
    unittest.main()

ตารางตัดสินใจ

เงื่อนไข	วิธี	เวลา	auxiliary memory	ข้อแลกเปลี่ยน
default/readability	deque BFS	O(n)	O(w)	level boundary ชัด
ไม่อยาก import deque	list + head	O(n)	O(n)	list เก็บ node ที่ผ่านแล้ว
tree ไม่ลึกและโค้ด DFS มีอยู่	DFS by depth	O(n)	O(h)	เสี่ยง recursion limit

best default คือ deque BFS เพราะตรงกับคำว่า level order และ memory สัมพันธ์กับ frontier จริง DFS ใช้ได้แต่ต้นไม้เอียงลึกอาจชน recursion limit ส่วน list+head เร็วแต่ไม่คืน memory ด้านหน้าจนจบ

ถ้าข้อมูลเป็น stream ของ edges ที่ยังสร้าง tree ไม่ครบ ต้องกำหนด ordering และ storage เพิ่ม ไม่ใช่โยน iterator เข้า algorithm นี้ตรง ๆ edge cases ได้แก่ root ว่าง, node เดียว, tree เอียง และ level กว้างมาก

Recap

• จับขนาด queue ก่อนเริ่ม level เพื่อกำหนด boundary
• ใช้ deque แทน pop(0)
• DFS สะสมตาม depth ได้แต่แลกกับ call stack
• memory ของ BFS ขึ้นกับความกว้าง ส่วน DFS ขึ้นกับความสูง
• เลือก deque BFS เป็น default ที่อ่าน intent ชัดที่สุด

ลองเพิ่ม test tree เอียงหนึ่งหมื่นระดับเพื่อเห็นความต่างของ recursion กับ iterative queue ด้วยตัวเองครับ