【数据结构和算法】BFS和DFS两种方式解决

1，BFS解决

其实这就是二叉树的BFS，也可以看下之前讲的373，数据结构-6,树 ，

就是这样，一层一层打印，使用队列解决

    public ArrayList<arraylist<integer>&gt; levelOrder(TreeNode root) {
        //边界条件判断
        if (root == null)
            return new ArrayList&lt;&gt;();
        //队列
        Queue<treenode> queue = new LinkedList&lt;&gt;();
        ArrayList<arraylist<integer>&gt; res = new ArrayList&lt;&gt;();
        //根节点入队
        queue.add(root);
        //如果队列不为空就继续循环
        while (!queue.isEmpty()) {
            //BFS打印，levelNum表示的是每层的结点数
            int levelNum = queue.size();
            //subList存储的是每层的结点值
            ArrayList<integer> subList = new ArrayList&lt;&gt;();
            for (int i = 0; i &lt; levelNum; i++) {
                //出队
                TreeNode node = queue.poll();
                subList.add(node.val);
                //左右子节点如果不为空就加入到队列中
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            //把每层的结点值存储在res中，
            res.add(subList);
        }
        return res;
    }

2，DFS解决

这题让一层一层的打印，其实就是BFS，但使用DFS也是可以解决的，看一下

    public ArrayList<arraylist<integer>&gt; levelOrder(TreeNode root) {
        ArrayList<arraylist<integer>&gt; res = new ArrayList&lt;&gt;();
        levelHelper(res, root, 0);
        return res;
    }

    public void levelHelper(ArrayList<arraylist<integer>&gt; list, TreeNode root, int level) {
        //边界条件判断
        if (root == null)
            return;
        //level表示的是层数，如果level &gt;= list.size()，说明到下一层了，所以
        //要先把下一层的list初始化，防止下面add的时候出现空指针异常
        if (level &gt;= list.size()) {
            list.add(new ArrayList&lt;&gt;());
        }
        //level表示的是第几层，这里访问到第几层，我们就把数据加入到第几层
        list.get(level).add(root.val);
        //当前节点访问完之后，再使用递归的方式分别访问当前节点的左右子节点
        levelHelper(list, root.left, level + 1);
        levelHelper(list, root.right, level + 1);
    }

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》