list转tree递归转换
/** * 递归遍历节点 * @param sourceList * @param parentCode * @return */ public List<Office> findChildrenList(List<Office> sourceList, String parentCode) { List<Office> treeList = new ArrayList<>(); //获取到所有parentCode的子节点 for(Office item:sourceList) { if (parentCode.equals(item.getParentCode())) { treeList.add(item); //递归遍历该子节点的子节点列表 item.setChildList(this.findChildrenList(sourceList,item.getOfficeCode())); } } return treeList; }
假设有列表有n个元素要组成一颗树,时间复杂度为O(n2), 每次递归都会创建一个treeList对象,空间复杂度为O(n)
这个递归可能当数据量太大时会造成方法栈内存溢出,不是很想使用这个方法。
双重for循环转tree(改进)
/** * 部门列表数据转换成树结构 * 一次性把所有根节点获取到,然后再获取 * * @param list * @param parentCode * @return */ public List<Office> convertTree(List<Office> list, String parentCode) { List<Office> trees = new ArrayList<>(); for (Office item : list) { //获取到根节点 if (parentCode.equals(item.getParentCode())) { trees.add(item); } //遍历获取所有节点下的子节点数据,去除子节点列表中的重复数据 for (Office it : list) { if (it.getParentCode().equals(item.getId())) { if (item.getChildList() == null) { item.setChildList(new ArrayList<Office>()); } boolean isPut = true; for (Office childItem : item.getChildList()) { if (it.getOfficeCode().equals(childItem.getOfficeCode())) { isPut = false; } } if (isPut) { item.getChildList().add(it); } } } } return trees; }
上面双重for循环,总的来及应该算三重for循环,最外层循环的作用是,获取到根节点为parentCode的字节点作为树字节的root树根节点。
还有一个作用是,遍历所有节点的子节点列表,
第二层for循环就是用来查找节点的字节点。
而第三层循环是用来去去除子节点列表中的重复数据。因为当List<Office> list是被缓存到内存中时,再次将这个list数据进行树转换就会造成子节点数据重复
参考资料
java list 转树 tree 的三种写法:https://blog.csdn.net/jcroad/article/details/79735790#commentBox