如何遍历未知深度对象并按字符串过滤保留匹配节点及父级分支

核心逻辑 #

采用深度优先的后序遍历处理，不需要提前知道嵌套深度，从最底层子节点向上做匹配校验，规则如下：

• 处理任意节点时，先递归过滤它的所有子节点，拿到子节点层的有效结果
• 只要满足两个条件之一就保留当前节点：
  • 当前节点自身的name字段包含目标匹配字符串
  • 当前节点过滤后的子节点列表不为空（说明子树里存在匹配项，当前节点是匹配节点的上级链路节点，必须保留）
• 两个条件都不满足的节点直接丢弃，自动裁剪掉无关分支

完整TypeScript实现 #

export interface Role {
  children: Role[];
  name: string;
}

function filterRoleTree(roleList: Role[], searchKey: string): Role[] {
  const validNodes: Role[] = [];
  for (const node of roleList) {
    // 先递归处理子节点，拿到子层过滤结果
    const validChildren = filterRoleTree(node.children, searchKey);
    // 校验当前节点是否需要保留
    const selfMatched = node.name.includes(searchKey);
    if (selfMatched || validChildren.length > 0) {
      validNodes.push({
        ...node,
        children: validChildren
      });
    }
  }
  return validNodes;
}

效果说明 #

举个实际场景的例子：如果传入的树里第4层某个节点name包含搜索关键词，函数会自动保留这个节点本身，以及从根节点到这个节点路径上的所有父节点，路径外的所有其他分支都会被移除，不会出现父节点丢失或者无关分支残留的问题。
如果需要处理大小写不敏感的匹配，只需要把node.name.includes(searchKey)改成node.name.toLowerCase().includes(searchKey.toLowerCase())即可。

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