一、題目描述

給定一個N叉樹的根節點，返回其節點值的前序遍歷結果。前序遍歷的定義是：先訪問根節點，再依次遍歷每個子節點（從左到右）。例如，對于如下N叉樹：

    1/ | \3  2  4
/ \
5  6

前序遍歷結果為：[1,3,5,6,2,4]。

二、核心難點：null指針與迭代邏輯的設計

難點1：null指針的作用——標記節點處理階段

在迭代法中，我們需要模擬遞歸的“回溯”過程。null指針在此充當階段分隔符，用于區分以下兩個階段：

1. 入棧子節點階段：當遇到非null節點時，先將所有子節點逆序入棧，再將當前節點和null入棧，標記“子節點已入棧，等待處理當前節點值”。
2. 收集節點值階段：當遇到null時，說明其前一個節點的子節點已全部入棧，此時彈出該節點并收集值（類似遞歸中的“回溯時處理”）。

難點2：迭代邏輯的核心——棧的狀態控制

• 子節點逆序入棧：由于棧是后進先出（LIFO），將子節點按逆序入棧（如[C,B,A]入棧，彈出順序為A,B,C），確保前序遍歷的順序（根→A→B→C）。
• 雙棧操作：通過“非null節點入棧子節點→入棧自身和null”的模式，確保在處理完所有子節點后，才會處理當前節點值，避免重復訪問。

三、代碼解析：迭代法的完整實現

import java.util.*;class Solution {public List<Integer> preorder(Node root) {List<Integer> res = new ArrayList<>();if (root == null) return res;Stack<Node> stack = new Stack<>();stack.push(root); // 根節點入棧while (!stack.isEmpty()) {Node node = stack.pop(); // 彈出節點if (node != null) {// 1. 逆序入棧所有子節點if (node.children != null) {for (int i = node.children.size() - 1; i >= 0; i--) {stack.push(node.children.get(i));}}// 2. 入棧當前節點和null（標記處理階段）stack.push(node);stack.push(null);} else {// 遇到null，說明前一個節點的子節點已處理完畢，收集當前節點值Node valNode = stack.pop();res.add(valNode.val);}}return res;}
}

四、迭代流程模擬：以示例N叉樹為例

初始狀態

• 棧：[1]
• 結果：[]

第一次循環

1. 彈出1（非null）：
   • 子節點為[3,2,4]，逆序入棧為4,2,3。
   • 入棧1和null，棧變為：[4,2,3,1,null]。

第二次循環

1. 彈出null：
   • 彈出1，加入結果[1]。
   • 棧變為：[4,2,3]。

第三次循環

1. 彈出3（非null）：
   • 子節點為[5,6]，逆序入棧為6,5。
   • 入棧3和null，棧變為：[4,2,6,5,3,null]。

第四次循環

1. 彈出null：
   • 彈出3，加入結果[1,3]。
   • 棧變為：[4,2,6,5]。

第五次循環

1. 彈出5（非null，無子節點）：
   • 入棧5和null，棧變為：[4,2,6,5,null]。

第六次循環

1. 彈出null：
   • 彈出5，加入結果[1,3,5]。
   • 棧變為：[4,2,6]。

后續循環

• 類似流程處理6、2、4，最終結果為[1,3,5,6,2,4]。

五、關鍵知識點：前序與后序迭代法的對比

前序遍歷（當前代碼）

• 核心邏輯：
  非null節點→逆序入棧子節點→入棧自身和null
  確保先處理子節點，再通過null觸發收集當前節點值。

后序遍歷（修改版代碼）

public List<Integer> postorder(Node root) {List<Integer> res = new ArrayList<>();if (root == null) return res;Stack<Node> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {Node node = stack.pop();if (node != null) {stack.push(node); // 先入棧當前節點stack.push(null); // 標記后序處理// 正序入棧子節點（與前序相反）if (node.children != null) {for (Node child : node.children) {stack.push(child);}}} else {Node valNode = stack.pop();res.add(valNode.val); // 后序收集}}return res;
}

• 關鍵修改：
  1. 子節點正序入棧（前序為逆序），確保后序遍歷順序（左→右→根）。
  2. null標記后處理當前節點，確保子節點先被處理。

六、null指針的本質：模擬遞歸的壓棧與回溯

遞歸流程	迭代（棧+null）模擬
調用preorder(root)	stack.push(root)
遞歸前序遍歷子節點	逆序入棧子節點，壓棧root和null
回溯時處理root.val	遇到null，彈出root并收集值

null指針的作用相當于遞歸中的“回溯點”，通過棧的狀態機控制，將遞歸的隱式調用棧轉化為顯式的棧操作，實現非遞歸算法。

七、總結：迭代法的優勢與適用場景

優勢

• 空間可控：避免遞歸深度過大導致的棧溢出（如樹高為1e5時）。
• 靈活性：可方便修改為后序、層序等其他遍歷方式（只需調整入棧順序和標記邏輯）。

適用場景

• 所有需要深度優先遍歷（DFS）的樹結構問題，尤其是N叉樹（遞歸可能復雜）。
• 面試中要求“非遞歸”解法的場景。

核心思想

通過棧模擬遞歸的調用棧，利用null等標記符區分節點的“預處理階段”和“回溯處理階段”，實現對遍歷順序的精確控制。理解這一思想后，可舉一反三解決二叉樹、N叉樹的各種遍歷問題。