Java中打印字典树（Trie）所有单词时出现重复与缺失问题求助

算力阿峰

2026-5-20

嘿，我之前在实现Trie的单词遍历功能时，也踩过几乎一模一样的坑！咱们来拆解一下问题大概率出在哪，以及怎么修复。

最可能的几个问题点

1. 遍历逻辑没区分「单词结束节点」

你提到插入时会在最后一个字母节点存完整单词，但如果遍历的时候不管这个节点是不是单词结尾，只要看到有word值就往列表里加，那肯定会重复。比如如果你的Trie里有"app"和"apple"，遍历到"app"的结尾节点会加一次"app"，到"apple"的结尾节点又加一次"apple"——但如果"app"本来不是你要存的单词，那就是插入时错误标记了结尾；如果两个都是有效单词，那没问题，但要是你没判断isEnd就乱加，可能把中间节点误存的单词也加进去了。

2. 静态ArrayList的“累积”坑

用静态的ArrayList存结果是个大隐患！如果每次遍历前不清空这个静态列表，之前的单词会一直留在里面，导致重复；甚至递归过程中如果分支处理不当，同一个单词可能被多个递归路径重复添加。

3. 插入时错误地给非结尾节点存了单词

比如插入"apple"时，你可能在遍历每个字母节点时都把"apple"存进去了，而不是只在最后一个'e'节点存。这样遍历的时候，每个节点都有同一个单词，自然会重复添加。

修复方案（附代码示例）

先从定义正确的Trie节点开始，明确区分「结尾标记」和「单词存储」：

class TrieNode {
    TrieNode[] children;
    boolean isEnd; // 标记该节点是否是某个单词的结尾
    String word; // 只有isEnd为true时，才存储完整单词

    public TrieNode() {
        children = new TrieNode[26]; // 假设只处理小写英文字母
        isEnd = false;
        word = null;
    }
}

然后是正确的插入逻辑，只在单词的最后一个节点标记结尾并存储单词：

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (current.children[idx] == null) {
                current.children[idx] = new TrieNode();
            }
            current = current.children[idx];
        }
        // 只有最后一个节点标记为结尾，并存储完整单词
        current.isEnd = true;
        current.word = word;
    }
}

最后是遍历逻辑，只在遇到结尾节点时才添加单词，并且用局部列表代替静态列表：

public List<String> getAllWords() {
    List<String> result = new ArrayList<>();
    traverse(root, result);
    return result;
}

private void traverse(TrieNode node, List<String> result) {
    if (node == null) {
        return;
    }
    // 只有当是单词结尾时，才把单词加入结果
    if (node.isEnd) {
        result.add(node.word);
    }
    // 递归遍历所有子节点
    for (TrieNode child : node.children) {
        traverse(child, result);
    }
}

快速排查小技巧

插入几个测试单词后，打印每个节点的isEnd和word值，确认只有最后一个节点有正确的单词和isEnd=true。
把静态ArrayList换成局部变量，每次遍历都新建一个列表，避免数据累积。
在遍历添加单词的地方加个日志，看看是不是同一个节点被多次触发添加。

这样调整后，应该就能解决重复和缺失的问题啦！

内容的提问来源于stack exchange，提问作者KONADO