題目描述:層序遍歷二元樹,回傳每一層節點值的列表(二維陣列)。
解題思路:BFS 搭配佇列:每次處理完整一層。在每輪迭代開始時,記錄當前佇列大小(即當前層的節點數),出佇列剛好那麼多節點、記錄值、將子節點入佇列。這樣每層的節點自然分組。
時間複雜度:O(n) — 每個節點入佇列和出佇列各一次。
空間複雜度:O(w),w 為最大層寬 — 佇列最多同時存一層的節點。
1. If root null: return [] 2. Queue = [root] 3. While queue non-empty: a. levelSize = queue.size() b. For i in [0, levelSize): pop node, record value, enqueue children c. Append level to result 4. Return result
遞迴 DFS O(n) 時間,O(h) 空間:遞迴訪問,層數作參數 — 邏輯相同但用遞迴堆疊而非隊列。
雙向隊列 Deque O(n) 時間,O(w) 空間:代替單向隊列,允許額外操作 — 對此題無益。