Trie数据结构单词提取异常：extractWords函数无法返回全部单词

你的extractWords函数仅返回第一个遍历到的单词，核心问题出在递归函数的循环逻辑里：

• 处理非*的键（比如b节点下的l）时，直接通过return recursion(x, currentWord + key)终止了整个循环，导致同一节点下的其他子节点（比如b节点下的o分支）完全没被遍历。
• 手动控制i的递增逻辑，增加了代码复杂度和出错概率。

解决步骤 #

1. 不要直接返回递归结果：将递归返回的单词数组合并到当前的results中，继续循环处理剩余的键，确保所有分支都被遍历。
2. 简化循环递增逻辑：把for循环的i递增改回常规的i++，避免手动控制带来的逻辑混乱。

修正后的代码 #

type Word = string;
type Words = Word[];

type TriNode = {
  [key: string]: TriNode | null;
};

let currentNode: TriNode = {
        '*': null,
        b: {
          l: {
            e: {
              '*': null,
            },
          },
          o: {
            u: {
              t: {
                '*': null,
              },
            },
          },
        },
      };

const extractWords = (triNode: TriNode): Words => {
  const recursion = (triNode: TriNode, currentWord: Word): Words => {
    const keys = Object.keys(triNode);
    let results: Words = [];
    for (let i = 0; i < keys.length; i++) {
      const key = keys[i];
      if (key === '*') {
        results.push(currentWord);
      } else {
        const childNode = triNode[key];
        if (childNode) {
          // 合并递归结果，而非直接终止循环
          results = results.concat(recursion(childNode, currentWord + key));
        }
      }
    }
    return results;
  };

  return recursion(triNode, '');
};


if (currentNode) {
  const r = extractWords(currentNode);
  console.log(r); // 输出 ["", "ble", "bout"]
}

额外说明 #

修正后的代码会包含空字符串，因为根节点的*: null代表空字符串是一个有效单词。如果不需要空字符串，只需修改*分支的判断逻辑：

if (key === '*' && currentWord) {
  results.push(currentWord);
}

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