如何用 Trie 按字典序遍历字符串？为什么它天然适合有序输出？
简化版
Trie 可以按字典序输出字符串，因为从根到节点的路径本身就是前缀。
只要在 DFS 时按照字符从小到大的顺序访问孩子节点，每次遇到单词结束节点就输出当前路径，得到的就是字典序结果。
如果孩子用数组存储，按下标 0..25 遍历即可；如果用 Map，需要先对 key 排序。
详细版
字典序比较的核心是先比较第一个不同字符。如果一个字符串是另一个的前缀，短的排前面。
Trie 刚好把相同前缀聚集在一起。按字符顺序 DFS 时，会先输出较小字符分支下的所有单词，再输出较大字符分支。
dfs(node, path):
if node.isEnd:
output(path)
for ch in sortedChildren:
dfs(child, path + ch)| 条件 | 作用 |
|---|---|
| 先判断 isEnd | 保证短前缀单词先输出 |
| 孩子按字符顺序遍历 | 保证整体字典序 |
所以 Trie 很适合词典、自动补全候选排序等场景。
完整版教学
1. 字典序到底比较什么
字典序不是按长度排序，而是从左到右比较字符。
例如：
app < apple < banana因为 app 是 apple 的前缀，所以短的 app 更靠前。
Trie 的路径天然表示前缀，因此非常适合处理这种顺序。
2. 为什么 Trie 能聚合同前缀
在 Trie 中，共享前缀的字符串会走同一段路径。
例如：
app
apple
ape它们都经过 a -> p，之后才分叉。
Trie 的字典序遍历，本质上是按字符顺序遍历一棵前缀树。
3. DFS 为什么可以输出完整单词
DFS 从根一路往下走，路径上的字符拼起来就是当前前缀。
当节点标记 isEnd = true 时，说明当前路径刚好是一个单词，可以输出。
path = "app"
node.isEnd = true
输出 app然后继续往更深处走，就能输出 apple。
4. 为什么要先输出当前节点再访问孩子
如果当前节点是单词结束，同时它还有孩子，说明当前单词是后续单词的前缀。
例如：
app
apple字典序里 app 应该在 apple 前面。所以 DFS 应该先检查当前节点的 isEnd，再访问孩子。
如果先访问孩子，就会把长词排到短词前面。
5. 孩子顺序为什么重要
如果孩子顺序乱了，输出也会乱。
数组孩子可以天然按下标遍历：
for i in 0..25:
if children[i] != null:
dfs(children[i])Map 孩子则通常要排序：
for ch in sort(children.keys):
dfs(children[ch])这也是数组 Trie 在固定字符集下更容易做有序遍历的原因。
6. 复杂度怎么分析
如果要输出所有字符串，总时间至少和输出内容总长度相关。
可以回答：
| 操作 | 复杂度 |
|---|---|
| 遍历节点 | O(numberOfNodes) |
| 输出字符串 | O(totalOutputLength) |
| Map 孩子排序 | 取决于每个节点孩子数 |
如果孩子用有序结构维护，遍历时就不需要额外排序，但插入成本可能更高。
7. 自动补全里怎么用
自动补全通常先走到前缀节点，再从该节点开始按字典序 DFS。
prefix = "ap"
找到 ap 节点
DFS 输出 app, apple, ape ...如果只需要前 K 个候选，可以输出够 K 个就停止，避免遍历整棵子树。
8. 常见误区与追问
- 误区：Trie 遍历天然就是字典序。 只有孩子按字符顺序访问时，结果才是字典序。
- 误区：应该先访问孩子再判断 isEnd。 当前单词是后续单词前缀时，短词应该先输出。
- 误区：Map 存孩子也会自动有序。 普通哈希表不保证顺序，需要排序或使用有序 Map。
- 追问：只要前 K 个结果怎么办？ DFS 过程中计数，输出 K 个后提前停止。
- 追问：字典序遍历的成本是多少？ 至少与访问节点数和输出总字符数相关，不能只看单词数量。