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

菜单树

菜单树的实现分析

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);
	    }
     // 广度优先遍历

     public List<String> binaryTreePaths(TreeNode root) {
        if(root==null) {
            return new ArrayList<String>();
        }
        //res是最终结果集，queue中存放的是封装的Pair对象
        List<String> res = new ArrayList<String>();
        Queue<Pair> queue = new LinkedList<Pair>();
        queue.offer(new Pair(root,""));
        while(!queue.isEmpty()) {
            Pair p = queue.poll();
            String path = p.path;
            TreeNode node = p.node;
            if(node==null) {
                continue;
            }
            //如果当前节点是叶子节点，将其拼装后放入最终结果集中
            if(node!=null && (node.left==null && node.right==null)) {
                res.add(path+node.val);
                continue;
            }
            //如果当前节点不是叶子节点，将其左子树和新路径放入队列中
            if(node.left!=null) {
                queue.offer(new Pair(node.left,path+node.val+"->"));
            }
            //如果当前节点不是叶子节点，将其右子树和新路径放入队列中
            if(node.right!=null) {
                queue.offer(new Pair(node.right,path+node.val+"->"));
            }
        }
        return res;
    }
    //自定义一个Pair对象，封装TreeNode和临时路径Path
    class Pair {
        private TreeNode node;
        private String path;
        Pair(TreeNode node,String path) {
            this.node = node;
            this.path = path;
        }
    }