前言

最近在做一个权限管理类的项目，在做首页菜单功能时，遇到一个问题：

当点击某个菜单时，页面顶部需要显示当前菜单的面包屑信息。

研究了一下，最后使用递归+回溯算法，完成了需求。感觉这个功能还挺常见的，在这里记录一下具体的方案，希望可以帮到大家，谢谢！

需求

面包屑导航其实就是这样的

这个功能还是挺常见的，具体效果就是：当打开某个菜单时，在页面的顶部 显示当前菜单的层级信息。一般是从当前菜单的根菜单开始。

例如：系统中菜单层级为：系统管理->权限管理->角色管理，那么当在点击角色管理菜单时，面包屑部分就会变成系统管理/权限管理/角色管理这样。

可以看出，所谓的面包屑数据，其实可以理解为就是当前菜单在整个菜单树中的全路径信息。

下面我们分步来实现：

1. 封装树形菜单数据
2. 封装菜单的面包屑全路径数据

准备工作

表设计

菜单表设计如下：

这应该算是最简单的菜单表的设计了，同时也插入了一些测试数据（这里规范了根菜单的父菜单id为0）：

代码

项目依赖为 SpringBoot v2.6.13，引入了mybatis-plus，如下，创建了菜单相关的实体类、dao层接口、service层接口，此外，还封装了一个菜单Vo。

@Data
@TableName("t_menu")
public class MenuEntity {
    @TableId(type = IdType.AUTO)
    private Integer id;
    private String name;
    private Integer parentId;
}

@Mapper
public interface MenuMapper extends BaseMapper<MenuEntity> {
}

public interface MenuService extends IService<MenuEntity> {
    List<MenuVo> listTree();
}

@Service
public class MenuServiceImpl extends ServiceImpl<MenuMapper, MenuEntity> implements MenuService {
}

菜单vo

@Data
public class MenuVo {
    /**
     * ID
     */
    private Integer id;
    /**
     * 菜单名称
     */
    private String name;
    /**
     * 子菜单集合
     */
    private List<MenuVo> subMenus;
}

代码实现

递归封装树形菜单

service层，定义了一个方法listTree，用来返回树形菜单数据

public interface MenuService extends IService<MenuEntity> {
    List<MenuVo> listTree();
}

实现类中，重写了该方法，通过递归的方式，完成了功能。

封装了一个方法getSubMenus，根据传入的parentId，获取它的子菜单的树形数据。实际就是递归调用本方法，这里就不再赘述。

@Service
public class MenuServiceImpl extends ServiceImpl<MenuMapper, MenuEntity> implements MenuService {
    /**
     * 返回树形菜单数据
     *
     * @return
     */
    @Override
    public List<MenuVo> listTree() {
        List<MenuEntity> list = list();
        return getSubMenus(list, 0);
    }

    /**
     * 根据传入的菜单id 封装子菜单树形数据
     *
     * @param list
     * @param parentId
     * @return
     */
    private List<MenuVo> getSubMenus(List<MenuEntity> list, Integer parentId) {
        return list.stream()
                //筛选出当前菜单id的直接子菜单
                .filter(menu -> parentId.equals(menu.getParentId()))
                .map(menu -> {
                    MenuVo vo = new MenuVo();
                    //封装vo
                    BeanUtils.copyProperties(menu, vo);
                    //通过递归的方式，封装当前菜单的子菜单
                    vo.setSubMenus(getSubMenus(list, menu.getId()));
                    return vo;
                }).collect(Collectors.toList());
    }
}

递归+回溯 封装面包屑信息

下面我们需要获取每一个菜单的面包屑信息，首先在MenuVo中新增一个属性，是一个List<String>集合，用来封装当前菜单的全路径数据。

例如，针对这个结构：系统管理->权限管理->角色管理，List集合中就会封装三个元素["系统管理","权限管理","角色管理"]。

@Data
public class MenuVo {
    /**
     * ID
     */
    private Integer id;
    /**
     * 菜单名称
     */
    private String name;
    /**
     * 子菜单集合
     */
    private List<MenuVo> subMenus;
    /**
     * 当前菜单层级信息：即面包屑数据
     */
    private List<String> titles;
}

对应MenuService中的方法也要进行修改：

@Service
public class MenuServiceImpl extends ServiceImpl<MenuMapper, MenuEntity> implements MenuService {
    /**
     * 返回树形菜单数据
     *
     * @return
     */
    @Override
    public List<MenuVo> listTree() {
        List<MenuEntity> list = list();
        return getSubMenus(list, 0, new ArrayList<>());
    }

    /**
     * 根据传入的菜单id 封装子菜单树形数据
     *
     * @param list
     * @param parentId
     * @return
     */
    private List<MenuVo> getSubMenus(List<MenuEntity> list, Integer parentId, List<String> titles) {
        return list.stream()
                //筛选出当前菜单id的直接子菜单
                .filter(menu -> parentId.equals(menu.getParentId()))
                .map(menu -> {
                    MenuVo vo = new MenuVo();
                    //封装vo基本数据
                    BeanUtils.copyProperties(menu, vo);
                    //将当前层级的菜单名称添加到titles
                    titles.add(menu.getName());
                    //记录上一步中 添加到集合中的元素下标：之后要根据这个下标做回溯操作
                    int index = titles.size() - 1;
                    //将当前菜单的面包屑信息进行封装
                    vo.setTitles(new ArrayList<>(titles));
                    //递归封装子菜单
                    vo.setSubMenus(getSubMenus(list, menu.getId(), titles));
                    //进行回溯操作，将截止到当前层级封装的菜单名称全部删除。避免在下次递归中影响其他分支的数据
                    titles.subList(index, titles.size()).clear();
                    return vo;
                }).collect(Collectors.toList());
    }
}

上面的代码中：

• getSubMenus方法新增了一个参数List<String> titles，这个List集合的作用就是：将每一层的菜单名称封装到里面，方便它的每一个子菜单去获取。
• 第30行：将当前层的菜单名称，添加到titles中。
• 第32行：记录了上一步中，封装的菜单名称的下标。（因为之后要从这个位置开始回溯）
• 第34行：创建一个新的List集合，将titles中的数据复制到里面，然后赋值给vo里面的titles属性。（这里是因为如果直接将titles赋值到vo中，因为这是一个共享变量，所以最后会导致所有菜单的titles值都一样了。所以这里需要新建一个List集合。）
• 第36行：递归调用时，将共享变量titles，继续进行了传入。
• 第38行：这里是进行了回溯操作，这行代码的作用，一句话来概括：通过将已遍历过的分支数据进行回退，避免影响其他分支的数据收集。个人认为，这是回溯算法的重要思想。下面简单介绍一下回溯算法。

可以看一下，上面的代码封装出来的结果是正确的：各位也可复制代码自行测试。

回溯算法

在介绍回溯算法之前，我们可以先看一下：如果不进行回溯，会发生什么。

我们将代码中回溯的部分删除，然后再看一下执行结果：代码如下

    private List<MenuVo> getSubMenus(List<MenuEntity> list, String parentId, List<String> titles) {
        return list.stream().filter(menu -> parentId.equals(menu.getParentId()))
                .map(menu -> {
                    MenuVo vo = new MenuVo();
                    //封装vo基本数据
                    BeanUtils.copyProperties(menu, vo);
                    //将当前层级的菜单名称添加到titles
                    titles.add(menu.getName());
                    //将当前菜单的面包屑信息进行封装
                    vo.setTitles(new ArrayList<>(titles));
                    //递归封装子菜单
                    vo.setSubMenus(getSubMenus(list, menu.getId(), titles));
                    return vo;
                }).collect(Collectors.toList());
    }

执行结果：

可以很清楚的看出：在日志管理这棵菜单树中，操作日志的封装没有问题，但是登录日志的面包屑数据中，多了一个操作日志。

这显然是不对的，登录日志的全路径，应该是["日志管理","登录日志"]才对啊，为什么中间多了一个操作日志呢。

这其实是因为，我们在递归的过程中，使用了一个共享变量titles，在递归的过程中，他会把每一个菜单的名称都进行收集，以日志管理这棵菜单树为例：

• 当指针遍历到日志管理：titles.add("日志管理")；此时 titles=["日志管理"]
• 当指针遍历到操作日志：titles.add("操作日志")；此时 titles=["日志管理","操作日志"]
• 当指针遍历到登录日志：titles.add("登录日志")；此时 titles=["日志管理","操作日志","登录日志"]

不难看出，当遍历到登录日志时，由于之前已经遍历过操作日志这个菜单，所以titles中封装了多余的数据，所以导致登录日志的全路径中出现了操作日志。

怎么解决这个问题呢？这里就可以引入回溯的操作：

我们可以 在遍历完操作日志之后，在遍历登录日志之前，将"操作日志"从titles中删除掉。这样，在遍历登录日志之前，titles=["日志管理"]，遍历完登录日志之后，titles=["日志管理","登录日志"]，这样，问题就迎刃而解了。

总结：在代码中，我们每递归完一个子菜单，都要去回溯titles，保证在下次递归之前，titles中只封装了本层菜单的数据，这样就可以避免出现多余数据的问题。

拓展：递归+回溯 收集树节点全路径

上面的这个解决方案，可以用在很多相同的场景。比方说在通过递归封装一棵树的时候，如果想顺带收集一下每个节点的全路径信息，这个方案都可以适用。

拓展：代码优化 规避线程安全问题

上面其实有点把问题复杂化了，并且引入了共享变量titles，有可能会出现线程安全问题。

在这里，代码进行了一些优化，之前需要进行回溯是因为全局使用了一个共享变量titles，并层层向下传递。现在，每层的都创建一个新的List集合，仅传递到下一层。

    private List<MenuVo> getSubMenus(List<MenuEntity> list, String parentId, List<String> titles) {
        return list.stream().filter(menu -> parentId.equals(menu.getParentId()))
                .map(menu -> {
                    MenuVo vo = new MenuVo();
                    //封装vo基本数据
                    BeanUtils.copyProperties(menu, vo);
                    //将当前层级的菜单名称添加到titles
                    List<String> currentTitles = new ArrayList<>(titles);
                    currentTitles.add(menu.getName());
                    //将当前菜单的面包屑信息进行封装
                    vo.setTitles(currentTitles);
                    //递归封装子菜单
                    vo.setSubMenus(getSubMenus(list, menu.getId(), currentTitles));
                    return vo;
                }).collect(Collectors.toList());
    }

总结

总的来说，还是很兴奋的。之前刷过一段时间的算法题，一直觉得对于我这种CRUD Boy 用处不大。结果今天在业务开发中应用到了回溯算法，虽然可能没有多高级，但还是很高兴，感觉自己学到了很多。

感谢各位的阅读，文章中有不对的地方，感谢各位指正，谢谢~