目錄

1. 驗證棧序列

1.1 題目解析

1.2 解法

1.3 代碼實現

2. N叉樹的層序遍歷

2.1 題目解析

2.2 解法

2.3 代碼實現

---

1. 驗證棧序列

https://leetcode.cn/problems/validate-stack-sequences/description/

給定?pushed?和?popped?兩個序列，每個序列中的?值都不重復，只有當它們可能是在最初空棧上進行的推入 push 和彈出 pop 操作序列的結果時，返回?true；否則，返回?false?。

示例 1：

輸入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
輸出：true
解釋：我們可以按以下順序執行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

輸入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
輸出：false
解釋：1 不能在 2 之前彈出。

提示：

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• pushed?的所有元素?互不相同
• popped.length == pushed.length
• popped?是?pushed?的一個排列

1.1 題目解析

題目本質：
判斷一對 pushed / popped 序列能否由同一“從空開始”的棧操作產生。抽象成：按 pushed 順序“盡量入棧”，每當棧頂等于 popped 的下一個元素就立刻出棧，最終是否能把 popped 全部匹配并清空棧。

常規解法：
最直觀就是模擬棧：順序把 pushed[i] 入棧；每次入棧后，若棧頂恰好等于 popped[j]，就持續出棧并前進 j。

問題分析：
該題無需復雜數據結構，也不需要回溯。因為所有元素互不相同，且 popped 是 pushed 的一個排列，所以“能彈就彈”的貪心策略不會錯；若某個 popped[j] 遲遲在棧頂見不到，那就永遠見不到（后續只會把更多不同元素壓在它上面）。

思路轉折：
要想高效 → 直接一次線性掃描 + 棧模擬即可：

• 掃過 pushed 時入棧；

• 每次入棧后，盡可能匹配 popped 進行彈棧；

• 掃描結束后棧應為空（或 j == n）。
  時間 O(n)，空間 O(n)，是本題最優做法。

1.2 解法

算法思想：
維護指針 i 遍歷 pushed、指針 j 指向 popped 的下一個待彈元素；循環中把 pushed[i] 入棧，然后在 stack.peek() == popped[j] 時不斷 pop() 與 j++；最終棧空則返回 true。

i）初始化空棧，i = 0, j = 0。

ii）外層循環：當 i < pushed.length：

• push(pushed[i])，i++；

• 內層循環：當 stack.peek() == popped[j]：

  • pop()，j++。

iii）全部處理后，返回 stack.isEmpty()（或判斷 j == popped.length）。

易錯點：

• 等于就彈，且要連續彈：入棧后別忘了用 while 連續匹配 popped[j]，直到不等為止。

• 邊界與空棧判斷：寫 peek() 前要保證棧非空（示例代碼里通過條件順序或 isEmpty() 規避）。

• 指針前進時機：i 只在入棧后前進；j 只在成功彈出后前進。

1.3 代碼實現

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {// 可用 Deque<Integer> stack = new ArrayDeque<>(); 更高效java.util.Stack<Integer> stack = new java.util.Stack<>();int i = 0, j = 0, n = pushed.length;while (i < n) {stack.push(pushed[i++]);                 // 先按 pushed 順序入棧// 只要棧頂等于 popped[j]，就連續彈出并推進 jwhile (!stack.isEmpty() && stack.peek() == popped[j]) {stack.pop();j++;}}// 若能完全匹配，棧應被清空（等價于 j == n）return stack.isEmpty();}
}

復雜度分析：

• 時間復雜度：O(n)。每個元素最多入棧一次、出棧一次。

• 空間復雜度：O(n)。最壞情況下棧會臨時存放尚未匹配的元素。

2. N叉樹的層序遍歷

https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/

給定一個 N 叉樹，返回其節點值的層序遍歷。（即從左到右，逐層遍歷）。

樹的序列化輸入是用層序遍歷，每組子節點都由 null 值分隔（參見示例）。

示例 1：

輸入：root = [1,null,3,2,4,null,5,6]
輸出：[[1],[3,2,4],[5,6]]

示例 2：

輸入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
輸出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

• 樹的高度不會超過?1000
• 樹的節點總數在?[0,?104]?之間

2.1 題目解析

題目本質：
在一棵 N 叉樹上做層序遍歷（Level Order Traversal）：從根開始，逐層、從左到右收集結點值，形成二維列表。

常規解法：
用隊列做 BFS。根結點先入隊；每一輪“鎖定當前層的隊列大小 sz”，彈出 sz 個結點，把它們的值放到當前層列表，并把它們的子結點（若非空）全部入隊；層結束后把該層列表放進答案。。

問題分析：

• 本題沒有回溯或復雜剪枝，關鍵只是正確分層與子結點判空。

• 題目上限：節點數 ≤ 1e4、樹高 ≤ 1000。BFS 時間 O(n)、空間 O(w)（w 為最大寬度）都可接受。

• DFS 也能做層序（記錄 depth），但極深樹形遞歸層數會接近 1000，BFS 更穩妥。

思路轉折：
要想寫得又對又穩 → 一次線性 BFS + 鎖層大小：

• 入隊根；

• 循環直到隊空：先記 sz = q.size()，彈 sz 次組成一層；

• 遍歷子結點時判空，避免 NullPointerException 與把 null 入隊。

2.2 解法

算法思想：
維護隊列 q。
1）若 root == null 直接返回空結果；
2）root 入隊；
3）當隊列非空，令 sz = q.size()：循環 sz 次，彈出結點 node，把 node.val 記入本層；若 node.children != null，則將非空子結點依次入隊；
4）把本層列表加入答案。重復直至隊空。

步驟：

i）處理空樹：返回 []。

ii）初始化：Queue<Node> q = new ArrayDeque<>(); q.offer(root);

iii）外層循環：while (!q.isEmpty())：

• int sz = q.size(); List<Integer> level = new ArrayList<>(sz);

• 重復 sz 次：

  • Node node = q.poll(); level.add(node.val);

  • 若 node.children != null：遍歷每個子結點 ch，if (ch != null) q.offer(ch);

• result.add(level);

iiii）返回 result。

易錯點：

• children 判空：node.children 可能為 null，遍歷前要判空。

• 不要入隊 null：遍歷子結點時 if (ch != null) 再 offer。

• 鎖層大小：務必先取 sz = q.size()，再彈 sz 次，防止跨層污染。

• API 使用：隊列用 offer/poll/peek，不要用 pop（那是棧/雙端隊列當棧用的）。

• 實現類選擇：Queue 不能 new Queue<>()；用 ArrayDeque<>（相對 LinkedList 更高效、足夠）。

• 空樹返回值：不要返回 null，而是空列表。

• 泛型簡寫：new ArrayList<>()、new ArrayDeque<>() 更簡潔。

2.3 代碼實現

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) { val = _val; }public Node(int _val, List<Node> _children) {val = _val; children = _children;}
};
*/import java.util.*;class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result;  // 空樹Queue<Node> q = new ArrayDeque<>();q.offer(root);while (!q.isEmpty()) {int sz = q.size();                   // 鎖定本層大小List<Integer> level = new ArrayList<>(sz);for (int i = 0; i < sz; i++) {Node node = q.poll();            // 出隊當前層結點level.add(node.val);if (node.children != null) {     // 判空再遍歷子結點for (Node ch : node.children) {if (ch != null) q.offer(ch);}}}result.add(level);                   // 收錄本層}return result;}
}

復雜度分析：

• 時間復雜度：O(n)，每個結點至多入隊/出隊一次。

• 空間復雜度：O(w)，其中 w 為樹在某一層的最大結點數（最壞 O(n)）。