递归写树错误记录

Aug 26, 2020·

2 min read

前一段时间, 有一个需求, 需要将组织机构树进行渲染. 在完成的过程中遇到了三个问题, 在此将问题记录一下.

问题1: 生成树时, 栈溢出;

问题2: 适配前端模糊搜索时候, 对集合的判空存在问题;

问题3: 适配前端模糊搜索时, 返回的检索路径错误;

前文

需求是渲染组织机构树, 其结构如下:

public class TreeVO {
    /**
     * 代码值
     */
    private String id;
    /**
     * 对应的内容
     */
    private String name;
    /**
     * 是否可点击
     */
    private boolean disabled = false;
    /**
     * 子集
     */
    private List<TreeVO> children;
}

最开始的时候, 是设定为一次性返回所有节点.

优先考虑的方案自然是使用递归写法去完成, 由于代码包含了我司大量的缓存特性, 在几经删减修改之前, 已经不具备可读性, 所以这里就不贴出源码了. 大致上就是找到根节点, 然后根据这个根节点去寻找它的子集(这里有使用进程内缓存, 不会操作数据库), 然后递归查找完成树的渲染.

问题1 生成树时, 栈溢出

其实不难猜到, 栈溢出大概率都是递归跳出判断存在问题. 经我检查后发现, 是我所使用的缓存存在问题, 导致存在一个节点的子集中又存在这个节点的情况, 最终导致无限递归, 栈溢出. 将这个有问题的缓存修改以后, 程序就正常了.

后又经测试发现, IE浏览器下, 内存占用达到1.2GB, 疑似是前端控件封装存在问题, 导致IE下内存溢出, 没有回收. 反馈给前端控件开发人员以后, 迟迟拿不出解决方案. 后经与前端开发人员沟通, 将组织机构树改为异步渲染了, 即点击一个节点后, 后来生成当前指定节点及该节点下单层子集的数据并返回. 如果用户不全部展开, IE下内存占用能减少到200M左右. 虽说还是很夸张, 但也是无奈之举.

问题2 适配前端模糊搜索时候, 对集合的判空存在问题

问题2 其实是因为在解决IE兼容情况时, 前端要求我写一个接口, 供前端模糊匹配. 然后将匹配的路径返回给前端. 这是什么意思呢?

我现在有一个树, 树的结构是:

A:
    A1:
        A11
        A12
    A2:
        A21
        A22
    A3:
        A31
        A32
    A4

现在用户输入一个字符X, 假设它可以同时匹配到 A12和A32两个节点, 此时我需要给前端返回的数据类似于:

{
  "A,A1,A12",
  "A,A3,A32"
}

这样做的原因, 主要是因为树中的节点名字可能会有重复的, 这样设计以后, 即便是重复的节点, 也可以让用户根据上下文去判断是否是自己想要输入那一个.

基于这点, 我就需要给前端返回搜索路径.

其实要解决这个问题也非常简单, 我们可以在递归遍历树时, 增加一个变量, 用于保存这个路径即可. 这里我为了方便后续根据前端要求的格式输出结果集, 我使用了ArrayList来保存这个搜索路径.

    private void findXXByXXName(String searchXXName, String XXId, List<String> resultIdList, List<TreeVO> resultList) {
        if (StringUtils.isEmpty(searchXXName)) {
            return;
        }
        TreeVO XXTree = XXService.getXXTree(XXId);
        if (null == XXTree) {
            return;
        }
        resultIdList.add(XXTree.getId());
        // 表示匹配到了
        if (StringUtils.contains(XXTree.getName(), searchXXName)) {
            resultList.add(new TreeVO(StringUtils.join(resultIdList, ","), XXTree.getName()));
              resultList.clear();
        }
        if (null == XXTree.getChildren()) {
            return;
        }
        for (TreeVO child : XXTree.getChildren()) {
            findXXByXXName(searchXXName, child.getId(), tempIdList, resultList);
        }
    }

但这个时候, 我每次拿到的结果集却是

{
  "A,A1,A11,A12",
  "A2,A21,A22,A31,A32"
}

这很明显与我最初的需求并不相符, 又写出了一个bug. 简单梳理了一下自己的逻辑, 发现是我集合判空的时候存在问题

if (null == XXTree.getChildren()) {
  return;
}

因为我在创建树的时候, 当无值的时候, 使用的是Collections.emptyList(), 所以不可能为null.

修改方案:

if (CollectionUtils.isEmpty(ayTree.getChildren())) {
  return;
}

问题3: 适配前端模糊搜索时, 返回的检索路径错误

准确来说, 其实问题2和问题3是一样的问题, 都是检索路径错误. 但问题3的原因和问题2的原因不同.

问题3的现象是如果出现多个匹配结果时, 后续的结果路径很短, 类似于:

{
  "A,A1,A12",
  'A32"
}

经过我简单的梳理以后发现, 其实问题点就在于我复用了这个resultIdList.我本意上是想要复用对象, 在匹配到以后将结果返回, 清空该对象中的元素, 重新装载, 减少对象的创建.

问题就出现在这个清空操作. 当我在遍历第三层的时候, 即A11 A12时, 此时结果集中保存了第一层A和第二层A1的结果集. 若此时我匹配到了A12, 那么第一层和第二层的数据就被清空了. 当我继续遍历到A32时, 这时候, A A3 这两个节点的数据已经不存在了.

修改方案:

    private void findXXByXXName(String searchXXName, String XXId, List<String> resultIdList, List<TreeVO> resultList) {
        if (StringUtils.isEmpty(searchXXName)) {
            return;
        }
        TreeVO XXTree = XXService.getAyTree(ayId);
        if (null == XXTree) {
            return;
        }
        resultIdList.add(XXTree.getId());
        // 表示匹配到了
        if (StringUtils.contains(XXTree.getName(), searchXXName)) {
            resultList.add(new TreeVO(StringUtils.join(resultIdList, ","), XXTree.getName()));
        }
        if (CollectionUtils.isEmpty(XXTree.getChildren())) {
            return;
        }
        for (TreeVO child : XXTree.getChildren()) {
            List<String> tempIdList = new ArrayList<>(resultIdList);
            findXXByXXName(searchXXName, child.getId(), tempIdList, resultList);
        }
    }

在每一层都新建一个集合对象, 然后将之前的所有搜索路径都进行保存即可. 这样就不会再出现丢失检索路径的问题了.

写到最后

文章中关于复现问题点的代码可能存在无法准确复现bug的情况.