【数据结构和算法】--N叉树中，返回某些目标节点到根节点的所有路径

一、前言

这么多年工作经历中，“数据结构和算法”真的是超重要，工作中很多业务都能抽象成某种数据结构问题。下面是项目中遇到的一个问题。
业务背景：
在一个复杂的N叉树目录上，通过模糊搜索只返回搜索到的【要返回完整的从root到目标节点】节点链路，以便外围系统直接使用
分析：
按照实际操作，模糊搜索只能搜索到需要的几个目标节点数据，但实际业务需要的是这些目标节点到根节点的结构，以便完美展示。

问题抽象：
N叉树中，找到所有目标节点到根节点的数据，并构建成tree结构返回。如下图，要返回这些目标节点到根节点的整个路径上的节点数据。

二、具体实现及拓展

完整的代码如下

 public void filterNodeFromTree(){//查询所有的【"有树形结构的"】列表数据List<NodeTreeDo> originList = new ArrayList<>();Map<String,NodeTreeDo> originMap = originList.stream().collect(Collectors.toMap(NodeTreeDo::getId,ma->ma));//目标节点idList<String> targetIds = new ArrayList<>();Set<String> curRootIdSet = new HashSet<>(); //收集某个目标节点到root的路径经过的所有节点for(String id : targetIds){if(curRootIdSet.contains(id)) continue;//已经经历过路径，跳过curRootIdSet.addAll(collectNeedNode(originMap,id));}//收集到所有需要的节点的id，然后在过滤多余的List<NodeTreeDo> needList = originList.stream().filter(k->curRootIdSet.contains(k.getId())).collect(Collectors.toList());//构建成treelistToTree(needList);}

2.1、递归-目标节点到根节点的路径数据

private Set<String> collectNeedNode(Map<String,NodeTreeDo> originMap,String targetId){Set<String> idResultSet = new HashSet<>();collectNeedNode(originMap,targetId,idResultSet);return idResultSet;}private boolean collectNeedNode(Map<String,NodeTreeDo> originMap,String targetId,Set<String> idSet){if(!originMap.containsKey(targetId)) return false;idSet.add(targetId);NodeTreeDo cur = originMap.get(targetId);return collectNeedNode(originMap,cur.getParentId(),idSet);}

2.2、list转换为tree结构

    private List<NodeTreeDo> listToTree(List<NodeTreeDo> originList){Map<String, List<NodeTreeDo>> nodeByPidMap = originList.stream().collect(Collectors.groupingBy(NodeTreeDo::getParentId));// 循环一次设置当前节点的子节点originList.forEach(node -> node.setChildren(nodeByPidMap.get(node.getId())));// 获取 一级列表return originList.stream().filter(k->"".equals(k.getParentId())).collect(Collectors.toList());}

2.3、tree转换为list结构

  private List<NodeTreeDo> treeToList(List<NodeTreeDo> treeList){List<NodeTreeDo> resultList = new ArrayList<>();for(NodeTreeDo node : treeList){getAllListFromChildren(node,resultList);}return resultList;}private void getAllListFromChildren(NodeTreeDo node,List<NodeTreeDo> resultList){NodeTreeDo copy = CommonUtil.transForm(node,NodeTreeDo.class);copy.setChildren(null); //深度拷贝后，把children设置为nullresultList.add(copy);if(CollectionUtils.isNotEmpty(node.getChildren())){for(NodeTreeDo temp : node.getChildren()){getAllListFromChildren(temp,resultList);}}//没子节点了，自动会退出}