589. N叉树的前序遍历迭代法：null指针与栈的巧妙配合-EW帮帮网

一、题目描述

给定一个N叉树的根节点，返回其节点值的前序遍历结果。前序遍历的定义是：先访问根节点，再依次遍历每个子节点（从左到右）。例如，对于如下N叉树：

前序遍历结果为：[1,3,5,6,2,4]。

二、核心难点：null指针与迭代逻辑的设计

难点1：null指针的作用——标记节点处理阶段

在迭代法中，我们需要模拟递归的“回溯”过程。null指针在此充当阶段分隔符，用于区分以下两个阶段：

入栈子节点阶段：当遇到非null节点时，先将所有子节点逆序入栈，再将当前节点和null入栈，标记“子节点已入栈，等待处理当前节点值”。
收集节点值阶段：当遇到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（非null）：
- 子节点为[3,2,4]，逆序入栈为4,2,3。
- 入栈1和null，栈变为：[4,2,3,1,null]。

第二次循环

弹出null：
- 弹出1，加入结果[1]。
- 栈变为：[4,2,3]。

第三次循环

弹出3（非null）：
- 子节点为[5,6]，逆序入栈为6,5。
- 入栈3和null，栈变为：[4,2,6,5,3,null]。

第四次循环

弹出null：
- 弹出3，加入结果[1,3]。
- 栈变为：[4,2,6,5]。

第五次循环

弹出5（非null，无子节点）：
- 入栈5和null，栈变为：[4,2,6,5,null]。

第六次循环

弹出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叉树的各种遍历问题。

589. N叉树的前序遍历迭代法：null指针与栈的巧妙配合