Java树遍历：Stack与Queue实现方式解析

本文深入解析了Java中树形结构遍历的核心实现细节，重点阐明了为何DFS需用ArrayDeque逆序入栈以保证左→右访问顺序、BFS必须使用poll()而非remove()来避免运行时异常，以及按层遍历时缓存queue.size()的必要性；同时纠正常见误区，如摒弃过时的Stack类、警惕路径回溯时的上下文缺失问题，并给出性能更优的实践方案，帮助开发者写出健壮、高效且符合直觉的非递归树遍历代码。

用 Stack 做 DFS 时，为什么子节点要逆序入栈？

因为 Stack 是后进先出，而多数人期望的 DFS 顺序（比如左→右→下）要求左子树先被访问。如果按自然顺序（左、右）压栈，右子树会先弹出，结果变成“右优先”。

• 正确做法：从右到左遍历子节点，依次 push；这样左子节点最后入栈、最先弹出
• 常见错误：直接 foreach 子列表并 push，导致遍历方向反了，调试时发现顺序和递归版对不上
• 注意 Stack 已过时，生产环境建议用 ArrayDeque（它实现了 Deque，但作为栈用比 Stack 快且线程安全）

示例关键片段：

Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
    Node node = stack.pop();
    visit(node);
    // 逆序入栈：先右后左
    for (int i = node.children.size() - 1; i >= 0; i--) {
        stack.push(node.children.get(i));
    }
}

用 LinkedList 或 ArrayDeque 实现 BFS 时，poll() 和 remove() 别混用

poll() 在队列为空时返回 null，remove() 则抛 NoSuchElementException —— 这在树遍历中极易引发未捕获异常，尤其当某层节点全为叶子时。

• BFS 循环体里必须用 poll()，配合 while (!queue.isEmpty()) 安全驱动
• 别用 queue.remove() 替代，哪怕你“确定”不为空；树结构动态性高，空指针或异常常出现在边界 case（如 root == null）
• ArrayDeque 比 LinkedList 作队列更快，无同步开销，且内存更紧凑；除非需要 listIterator()，否则没理由选后者

树节点设计不带 parent 字段，DFS 非递归时怎么回溯路径？

纯靠栈本身无法还原完整路径（比如找从根到某目标节点的路径），因为 Stack 只存节点引用，不记录“我是谁的孩子”。这时候得把上下文打包进去。

• 方案一：定义包装类 StackNode，含 node 和 path（List）字段，每次 push 时生成新 path
• 方案二：用两个栈同步操作——一个存 Node，一个存对应深度或父引用（轻量但易错）
• 性能提醒：path 复制有开销，若只关心存在性而非路径，就别存整条 list；改用布尔标记 + 父指针 map（需提前建好）更省

广度优先遍历时，按层处理（level-order）怎么避免重复计算 size？

常见写法是循环内用 queue.size() 控制本层节点数，但这个值在循环中会变——如果一边 poll 一边 add，size() 就不是初始值了。

• 正确姿势：进入每层前，先记下当前 queue.size()，用 for 循环固定次数处理，而不是 while + size 判断
• 错误现场：while (i++ < queue.size()) —— queue.size() 每次都重新算，导致多遍历下层节点
• 兼容性注意：Java 8+ 的 ArrayDeque size() 是 O(1)，但老版本或某些 Queue 实现可能是 O(n)，所以缓存 size 值既是逻辑需要，也是性能习惯

事情说清了就结束

好了，本文到此结束，带大家了解了《Java树遍历：Stack与Queue实现方式解析》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！