【二叉树 Java】二叉树的层序遍历

一、层序遍历定义：

按照每层进行遍历，从左至右，从上至下遍历树的节点，如下图所示

二、题目描述：

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

三、层序遍历解决思路：

我们之前在进行前序、中序与后序遍历的迭代写法中，都是用栈模拟的，但是层序遍历不一样，是用队列进行模拟的。

问题一： 为什么是队列，我们可以思考一下，对每层元素先进入的元素先被遍历到，比如上题的第三层元素 5 先进入，元素 5 也需要先被遍历到。而队列恰好就是一种先进先出的数据结构，因此用队列进行处理。

问题二：通过上面的分析，我们知道了可以用队列模拟二叉树的层序遍历， 那么接下来问题就来到了，我们如何记录遍历到第几层了尼，即如何确定单层遍历结束？

对这个问题，我们可以思考每次循环我们向队列中应该加入那些节点，每次循环向队列中加入的节点应该为上一层的所有节点的孩子节点按从左向右的顺序加入。因此，我们只需要记录上一层节点个数，即上一次循环结束队列的长度 size。在进行当次循环时，只需要依此遍历 size 个队列中的节点元素就可以结束了，对遍历到的每个节点元素，将其出队列，然后将其左右子节点加入队列中。遍历 size 次后当前层就完全遍历完毕，被加入到队列中。于此同时，当前层的上一层的所有节点也被从队列出移除。

四、代码：

    // 二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 存储结果的数组
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for(int i=0; i<size; i++){
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            res.add(new ArrayList<>(level));
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

五、层序遍历的应用

求二叉树的深度

求二叉树的深度，就是在二叉树层序遍历的基础上，在每一层遍历结束的时候将深度变量加1

    //最大深度
    public int maxDepth(TreeNode root) {
        int maxD = 0;
        if(root == null){
            return maxD;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                TreeNode treeNode = queue.poll();
                if(treeNode.left != null) queue.offer(treeNode.left);
                if(treeNode.right != null) queue.offer(treeNode.right);
            }
            maxD++; // 增加深度
        }
        return maxD;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19