IDDFS

1. 概述 IDDFS (Iterative deepening depth-first search)：迭代加深搜索，是一种状态空间/图的搜索策略。 其空间复杂度仅为 \( O(d) \)，相比用队列实现层序遍历所需的 \( O(b^d) \) 空间复杂度，极大地节约了空间开销，b 为分支因子，d 为深度。 从三个维度来分析，空间开销、时间性能和求解路径的代价，IDDFS 都接近最优，是一个非常优秀的算法。 本文主要介绍用 IDDFS 算法实现二叉树的层序遍历，如对其它方面的搜索运用感兴趣，可阅读参考资料1。 代码仓库：https://github.com/patricklaux/perfect-code 2. 使用队列实现层序遍历 层序遍历：即为按层顺序访问，所有深度为 d 的节点在深度为 d+1 的节点之前访问——（d, b, f, a, c, e, g）。 使用队列实现层序遍历并不复杂，代码如下： public void levelOrderTraversal(List<Tuple2<K, V>> kvs) { if (root == null) { return; } ArrayDeque<Node<K, V>> queue = new ArrayDeque<>(size.get() / 2); queue.push(root); while (!queue.isEmpty()) { Node<K, V> p = queue.poll(); kvs.add(Tuples.of(p.key, p.val)); if (p.left != null) { queue.offer(p.left); } if (p.right != null) { queue.offer(p.right); } } } 常见的算法书在介绍层序遍历时都采用队列来实现，这种算法被称为标准 BFS。 ...