树结构递归如何优化？

发布于
2023-04-20 陕西

翻到祖师爷代码，发现树结构的数据是后端通过递归去生成的，效率非常低，请问有什么方法可以优化吗？

public List<Map> createGroupTreeNode() {
    List<Map> childrenList = new ArrayList<Map>();
    getChildList(0L,childrenList);
    List<Map> treeList = new ArrayList<Map>();
    Map map = new HashMap();
    map.put("id", 0);
    map.put("text","根节点");
    map.put("isleaf", "0");
    map.put("icon", "fa fa-folder");
    Map subMap = new HashMap();
    subMap.put("opened", true);
    subMap.put("selected", true);
    map.put("state", subMap);
    map.put("children", childrenList);
    treeList.add(map);
    return treeList;  
}

public List<Map> getChildList(Long id,List<Map> childrenList){
    List<BaseGroup> childList = baseMapper.childListByParentId(id);
    if(childList != null && childList.size() > 0){
        List<Map> tempMap = new ArrayList<Map>();
        for(int i = 0; i < childList.size(); i++){
            List<Map> mylist = getChildList(childList.get(i).getId(),childrenList);
            Map map = new HashMap();
            if(mylist == null){
                map.put("id", childList.get(i).getId());
                map.put("text", childList.get(i).getNumber() + " - " + childList.get(i).getName());
                map.put("isleaf", "1");
                map.put("icon", "fa fa-folder");
                Map subMap = new HashMap();
                subMap.put("opened", false);
                map.put("state", subMap);
                tempMap.add(map);
            }else{
                map.put("id", childList.get(i).getId());
                map.put("text", childList.get(i).getNumber() + " - " + childList.get(i).getName());
                map.put("isleaf", "0");
                map.put("icon", "fa fa-folder");
                map.put("children", mylist);
                Map subMap = new HashMap();
                subMap.put("opened", false);
                map.put("state", subMap);
                tempMap.add(map);
            }
            if(id == 0){
                childrenList.add(map);
            }
        }
        return tempMap;
    }
    return null;
}

后端

java 优化树结构

阅读 3.5k

4 个回答

发布于
2023-04-21 四川

✓ 已被采纳

getChildList 的 childrenList 看起来是个输出参数，这里只有在 id == 0L 的时候会把元素加到 childrenList 中去。所以这个输入参数只在 id == 0L 的时候会使用。既然 getChildList 会把找到的列表返回出去，那完全不需要这个输出参数，在 createGroupTreeNode 里直接使用它的返回值就好。

public List<Map> createGroupTreeNode() {
    List<Map> childrenList = getChildList(0L);
//  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 不用初始化并作为输入参数传入，直接使用返回值就行
    // ....
}

public List<Map> getChildList(Long id) {
//                                   ^^^ 去掉 childrenList 参数
    
    // ...
    // if(id == 0){
    //     childrenList.add(map);
    // }
//  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 不需要了
}

总体来说，关于递归，就只有这一点问题。

然后在里面，for 循环中的循环变量 i 只有一个作用，就是 childList.get(i)，频繁的去使用 childList.get(i) 肯定不如缓存一个变量效率高，所以可以改为

for (int i = 0; i < childList.size(); i++) {
    BaseGroup it = childList.get(i);
    // 下面都用 it 代替 childList.get(i)
}

或者直接用增强 for 循环

 for (BaseGroup it : childList) {
     // ...
 }

另外在 for 循环中的 if 分支，比较一下发现只有一丁点区别，就是在处理 isleaf 和 children 的时候，所以可以把其他 .put 都提取出来，只处理有差异的部分

Map map = new HashMap();
map.put("id", it.getId());
// ...

List<Map> mylist = getChildList(it.getId());
// ^^^ 这句话后移到使用它的地方，不需要提前去取
//                 ^^^^^^^^^^^^^^^^^^^^^^^^ 没要第二个参数了，前面说过
if (mylist == null) {
    map.put("isleaf", "1");
}
else {
    map.put("isleaf", "0");
    map.put("children", mylist);
}