java中iterator接口本身不支持递归，但可通过栈模拟递归实现深度优先遍历迭代器：初始化压入根节点，next()弹出栈顶并逆序压入其子节点，确保左→右访问顺序。
Java 中的 Iterator 接口本身不支持递归，但你可以通过自定义迭代器类，在树形或嵌套结构（如多叉树、嵌套列表、JSON-like 对象等）中实现**深度优先遍历（DFS）风格的迭代器**。核心思路是用栈（Stack）模拟递归调用栈，避免真实递归带来的栈溢出风险，同时保持外部使用方式符合标准 Iterator 规范（hasNext() / next()）。
用栈模拟递归：非递归 DFS 迭代器
递归 DFS 天然适合树结构，但直接递归写成 Iterator 不可行（无法暂停/恢复执行）。替代方案是显式维护一个栈，保存待访问的节点。每次 next() 弹出栈顶节点，将其子节点（按逆序压入，保证左/先序顺序）推入栈中。
- 栈中存的是“下一步要访问的节点”，不是已访问过的
- 子节点需**逆序入栈**：比如孩子列表是 [A, B, C]，想按 A→B→C 访问，就应压入 C、B、A，这样弹出顺序才是 A、B、C
- 初始化时把根节点（或非空根集合）压入栈
示例：通用树节点的 DFS Iterator
假设你有如下简单树节点定义：
<font size="2"><pre class="brush:php;toolbar:false;">class TreeNode<t> {
T data;
List<treenode>> children = new ArrayList();
// 构造、getter 略
}</treenode></t>
对应 DFS 迭代器可这样写：
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
<font size="2"><pre class="brush:php;toolbar:false;">public class TreeDFSIterator<t> implements Iterator<t> {
private final Deque<treenode>> stack = new ArrayDeque();
<pre class="brush:java;toolbar:false;">public TreeDFSIterator(TreeNode<T> root) {
if (root != null) stack.push(root);
}
@Override
public boolean hasNext() {
return !stack.isEmpty();
}
@Override
public T next() {
TreeNode<T> node = stack.pop();
// 逆序压入子节点：保证从左到右访问
List<TreeNode<T>> children = node.children;
for (int i = children.size() - 1; i >= 0; i--) {
stack.push(children.get(i));
}
return node.data;
}
}
用法：for (String s : new Iterable() { public Iterator<string> iterator() { return new TreeDFSIterator(root); } }) { ... }</string> 或直接 new Iterator 实例循环。
扩展：支持多种嵌套结构（List of Lists、Map 嵌套等）
只要能抽象出“当前元素”和“它的子元素集合”，就能复用同一模式。例如嵌套 List<object></object>（含 String、List、Integer 等）：
- 把栈元素类型设为
Object -
next()取出一个元素；若它是List，就逆序把它的每个 item 压栈；否则直接返回该元素（即叶子） - 可加类型判断或 Visitor 接口统一处理不同嵌套类型
注意点与优化建议
-
线程安全：标准
Iterator不保证线程安全，如需并发访问，应加锁或用线程安全容器（如ConcurrentLinkedDeque替代ArrayDeque），但会牺牲性能 -
remove() 方法：默认抛
UnsupportedOperationException；如需支持，需在栈中保留父节点引用，实现真正删除逻辑（较复杂，通常不必要） - 内存占用：最坏情况（链状树）栈深为 O(n)，但远好于递归的函数调用栈开销
-
惰性计算：所有节点只在
next()时才展开，适合大数据量或动态生成子节点的场景
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
