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

一、前言

项目中接触一个问题：在大量有父子关系的列表中，需要筛选出特定约束的数据【要求某个目标节点延续到根节点的数据】。这个问题抽象为数据结构，就是：N叉树返回根节点到目标节点的路径

二、Java代码实现

  public void createTreeInfo(){//查询所有的  有树形结构的列表数据List<NodeTreeDo> originList = new ArrayList<>();//构建出每层level的父子关系Map<String, List<NodeTreeDo>> children = originList.stream().collect(Collectors.groupingBy(node -> node.getParentId()));originList.forEach(node -> node.setChildren(children.get(node.getId())));//过滤得到从根节点""出发的所有N叉树链路//   List<NodeTreeDo> collect = originList.stream().filter(k->"".equals(k.getParentId())).collect(Collectors.toList());List<NodeTreeDo> collect = originList.stream().filter(k->"".equals(k.getId())).collect(Collectors.toList()); //从根节点level=0层得到所有链路数据}public List<String> getPathFromRoot(NodeTreeDo root,String targetId){
//        NodeTreeDo root = new NodeTreeDo();
//        root.setParentId("");
//        root.setId("00001");
//        root.setChildren(new ArrayList<>()); //具体的tree结构，这里做模拟样例/*** root是完整的树形结构*/LinkedList<String> path = new LinkedList<>(); //找到从根节点到指定接定节点的路径getPathFromRoot(root,targetId,path);return path;}private boolean getPathFromRoot(NodeTreeDo root,String targetId, LinkedList<String> path){if(null == root) return false;String classid = root.getId();path.add(classid);if(classid.equals(targetId)) return true;boolean flag = false;List<NodeTreeDo> children = root.getChildren();if (null != children && !children.isEmpty()) {for (int i = 0; i < children.size(); i++) {if (!flag) {flag = getPathFromRoot(root.getChildren().get(i), targetId, path);}}}if (!flag) {path.remove(path.size() - 1);//孩子中都找不到，弹出栈顶元素}return flag;}