获取Trie中所有路径的路径中结束词的最大数量

// Trie节点定义
class TrieNode {
  constructor() {
    this.children = new Map(); // 使用Map保存子节点，key为字符，value为节点
    this.isEnd = false; // 是否为结束节点
  }
}

// Trie定义
class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // 插入字符串
  insert(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isEnd = true; // 标记结束节点
  }

  // 获取所有路径中结束节点的最大数量
  getMaxEndCount() {
    let maxEndCount = 0;

    // 辅助函数：递归遍历节点
    const traverse = (node, path, endCount) => {
      if (node.isEnd) {
        maxEndCount = Math.max(maxEndCount, endCount);
      }
      for (const [char, child] of node.children) {
        traverse(child, path + char, endCount + (child.isEnd ? 1 : 0));
      }
    };

    // 从根节点开始遍历
    for (const [char, child] of this.root.children) {
      traverse(child, char, child.isEnd ? 1 : 0);
    }

    return maxEndCount;
  }
}

// 示例用法
const trie = new Trie();
trie.insert("apple");
trie.insert("application");
trie.insert("app");
trie.insert("apt");
console.log(trie.getMaxEndCount()); // 输出：3