一、前言

在N叉树中，返回某些目标节点到根节点的所有路径这篇文章中，已经介绍一种查询目标节点到根节点的路径方法。现在思考用另一种方法去实现这个问题。

二、代码

2.1、Bean对象定义

public class ImprovedDoublyListNode {Set<String> idSet;Map<String,LinkedNode> idNodeMap;public ImprovedDoublyListNode(){}public ImprovedDoublyListNode(LinkedNode node){if(null == idSet){idSet = new HashSet<>();}if(null == idNodeMap){idNodeMap = new HashMap<>();}while (node != null) {idSet.add(node.cur_id);idNodeMap.put(node.cur_id,node);node = node.next;}}class LinkedNode {String cur_id;LinkedNode next;LinkedNode prev;public LinkedNode(String cur_id) {this.cur_id = cur_id;this.next = null;this.prev = null;}}
}

2.2、实现代码

把树形tree结构的数据，转换为双向链表后，能更快速找到“到根节点的链路”。

    //将所有叶子节点到根节点的路径转化为双向链表
public List<ImprovedDoublyListNode.LinkedNode> convertToDoublyLinkedLists(NodeTreeDo root) {List<ImprovedDoublyListNode.LinkedNode> result = new ArrayList<>();if (root == null) return result;// 遍历树并为每个叶子节点创建双向链表dfs(root, null, result);return result;}// 深度优先遍历树，构建双向链表
private void dfs(NodeTreeDo node, ImprovedDoublyListNode.LinkedNode head, List<ImprovedDoublyListNode.LinkedNode> result) {// 如果节点没有子节点，则是叶子节点if (CollectionUtils.isEmpty(node.getChildren())) {// 叶子节点，构建双向链表ImprovedDoublyListNode.LinkedNode listNode = new ImprovedDoublyListNode(). new LinkedNode(node.getId());// listNode.add(node.getId(),listNode);listNode.next = head; // 链接当前节点到链表头部if (head != null) {head.prev = listNode; // 设置双向链表的prev指针}result.add(listNode); // 将链表头节点加入结果列表return;}// 递归遍历子节点ImprovedDoublyListNode.LinkedNode currentNode = new ImprovedDoublyListNode(). new LinkedNode(node.getId());// currentNode.add(node.getId(),currentNode);currentNode.next = head; // 将当前节点添加到链表的头部if (head != null) {head.prev = currentNode; // 设置双向链表的prev指针}for (NodeTreeDo child : node.getChildren()) {// 递归调用DFS，遍历子节点dfs(child, currentNode, result);}}/*** * @param originNodeList* @return*/
public List<ImprovedDoublyListNode> convertListNode(List<ImprovedDoublyListNode.LinkedNode> originNodeList){List<ImprovedDoublyListNode> improvedList = originNodeList.stream().map(k->new ImprovedDoublyListNode(k)).collect(Collectors.toList());return improvedList;}/*** 输入任意节点id,找寻 到根节点的path* @param improvedList* @param inputId* @return*/
public ImprovedDoublyListNode.LinkedNode findNodePath(List<ImprovedDoublyListNode> improvedList,String inputId){ImprovedDoublyListNode.LinkedNode link = null;for(ImprovedDoublyListNode temp : improvedList){if(temp.idSet.contains(inputId)){//只要找到一个就可以link = temp.idNodeMap.get(inputId);break;}}return link;}/*** 转换为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());}

测试方法

 NodeTreeDo root = new NodeTreeDo("", "1", "Root");NodeTreeDo root1 = new NodeTreeDo("", "1.2", "Root111");NodeTreeDo child1 = new NodeTreeDo("1", "2", "Child 1");NodeTreeDo child2 = new NodeTreeDo("1", "3", "Child 2");NodeTreeDo child3 = new NodeTreeDo("2", "4", "Child 3");NodeTreeDo leaf1 = new NodeTreeDo("4", "5", "Leaf 1");NodeTreeDo leaf2 = new NodeTreeDo("4", "6", "Leaf 2");NodeTreeDo leaf3 = new NodeTreeDo("2", "2.1", "Child 4");NodeTreeDo leaf4 = new NodeTreeDo("2.1", "2.2", "Child 4");// 构建全部的list结构List<NodeTreeDo> rootList = new ArrayList<>();rootList.add(root);rootList.add(child1);rootList.add(child2);rootList.add(child3);rootList.add(leaf1);rootList.add(leaf2);rootList.add(leaf3);rootList.add(leaf4);rootList.add(root1);TreeToDoublyLinkedList solution = new TreeToDoublyLinkedList();List<NodeTreeDo> newRootList = solution.listToTree(rootList); //转换成树结构//每个叶子节点到根节点的链路improvedListList<ImprovedDoublyListNode> improvedList = new ArrayList<>();for(NodeTreeDo node : newRootList){List<ImprovedDoublyListNode.LinkedNode> result = solution.convertToDoublyLinkedLists(node);List<ImprovedDoublyListNode> oneList = solution.convertListNode(result);improvedList.addAll(oneList);}

在上面improvedList是每个叶子节点到根节点的链路，假设有一批目标节点targetIds，需要找到这些节点到根节点的路径

for(String teId : targetIds){ImprovedDoublyListNode.LinkedNode link = solution.findNodePath(improvedList,teId);// 打印path内容while (link != null) {System.out.print(link.cur_id + "->");link = link.next;}
}