业务中有很多时候需要用到菜单树的结构，比如菜单、评论系统等

菜单树

菜单树的实现分析

1.递归

菜单树的实现最原始的方法就是递归实现
数据量不是很到大的时候可以采用一次性将数据读取出存到list集合中，然后对该集合进行遍历。

		  
	/**
	 * 根据父节点的ID获取所有子节点
	 *
	 * @param list     分类表
	 * @param parentId 传入的父节点ID
     * @return String
     */
	  public List<Menu> getChildPerms(List<Menu> list, Long parentId) {
         List<Menu> returnList = new ArrayList<Menu>();
         list.stream().forEach(menu -> {
         // 一、根据传入的某个父节点ID,遍历该父节点的所有子节点
	         if (menu.getPId().equals(parentId)) {
	               recursionFn(list, menu);
	               returnList.add(menu);
	          }
	      });
	       return returnList;
	  }  
		  
	  /**
	   * 递归列表
	   *
	   * @param list
	   * @param t
	   */
	   private void recursionFn(List<Menu> list, Menu t) {
		   // 得到子节点列表
           List<Menu> childList = getChildList(list, t);
	       t.setChildren(childList);
	       childList.stream().forEach(tChild -> {
	           if (hasChild(list, tChild)) {
	                recursionFn(list, tChild);
	           }
	       });
	   }  
	 
	 /**
	  * 得到子节点列表
	  */
	 private List<Menu> getChildList(List<Menu> list, Menu t) {
	      List<Menu> tlist = new ArrayList<Menu>();
	      list.stream().filter(menu -> menu.getPId().equals(t.getId())).forEach(menu -> {
	            tlist.add(menu);
	      });
	      return tlist;
	 }
		
	 /**
	  * 判断是否有子节点
	  */
	 private boolean hasChild(List<Menu> list, Menu t) {
	     return getChildList(list, t).size() > 0 ? true : false;
	 }

2.生成树实现

思想： 自己查百度生成树的思想，只有将思想弄明白之后才能实现需求
实现思路：

  1. 首先将获得的list集合转成map集合 ；
  2. 遍历list集合
  3. 如果是根节点则直接存储到treelist中；
  4. 如果是非根节点，则找到当前对象的父级对象，将其添加到父级节点的child中报存；

  5. 时间复杂度O(N);

      
	   /**
	     * <p>
	     * 根据生成树的思想构建菜单树
	     *
	     * </P>
	     *
	     * @param list: 数据库获取符合条件的菜单列表
	     * @author: zhang.rongjun
	     * @DateTime: 8/9/2021 9:11 AM
	     * @return 菜单树
	     */
	    @Override
	    public List<Menu> getTreeByColl(List<Menu> list) {
	        Map<Long, Menu> map;
	        List<Menu> treelist = new ArrayList<>();
	        if (null == list || list.isEmpty()) {
	            return null;
	        }
	        //toMap()的第一个参数就是用来生成key值的，第二个参数就是用来生成value值的。
	        //第三个参数用在key值冲突的情况下：如果新元素产生的key在Map中已经出现过了，第三个参数就会定义解决的办法。
	        //如果k1与k2的key值相同，选择k1作为那个key所对应的value值。
	        map = list.stream().collect(Collectors.toMap(Menu::getId, a -> a, (k1, k2) -> k1));
	        // 将list集合对象转换为json的字符串
	        // 如果id是父级的话就放入tree中treelist
	        list.forEach(menu -> {
	            // 获取父级目录
	            if (map.get(menu.getPId()).equals(0L)) {
	                treelist.add(menu);
	            } else {
	                // 子级通过父id获取到父级的类型
	                Menu parent = map.get(menu.getPId());
	                // 父级获得子级，再将子级放到对应的父级中
	                parent.getChildren().add(menu);
	            }
	        });
	        return treelist;
	    }

拓展 二叉树的路径遍历

  
	    /**
	     * 257. 二叉树的所有路径
	     */
	    List<String> pathList = new ArrayList<>();
	    public List<String> binaryTreePaths(TreeNode root) {
	        getPathsDfs(root, "");
	        return pathList;
	    }
	    private void getPathsDfs(TreeNode root, String pre){
	        if (root == null){
	            return;
	        }
	        if (root.left == null && root.right == null){
	            pathList.add(pre + root.val);
	        }
	        String str = pre + "->" + root.val;
	        getPathsDfs(root.left, str);
	        getPathsDfs(root.right, str);
	    }