LeetCode.102 二叉树的层序遍历

题目描述

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

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

解题思路

对二叉树进行层序遍历即可，下一层的所有节点是当前层的所有左右子节点。用一个队列存储当前层的所有节点就好。

算法流程

1特例处理： 当根节点为空，则返回空列表 [] 。

2.初始化： 打印结果列表 res = [] ，包含根节点的队列 queue = [root] 。

3.BFS 循环： 当队列 queue 为空时跳出。
3.1新建一个临时列表 tmp ，用于存储当前层打印结果。
3.2当前层打印循环： 循环次数为当前层节点数（即队列 queue 长度）。

3.2.1出队： 队首元素出队，记为 node。
3.2.2打印： 将 node.val 添加至 tmp 尾部。
3.2.3添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue 。

3.3将当前层结果 tmp 添加入 res 。

4.返回值： 返回打印结果列表 res 即可。

代码解析

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //存储当前层所有节点的队列
        Queue<TreeNode> queue = new LinkedList<>();
        //结果集
        List<List<Integer>> res = new ArrayList();

        //如果当前根节点不为空，则加入队列，开始执行流程
        if(root != null){
            queue.add(root);
        }
        //当队列非空（当前层数有节点没有执行深度优先遍历）时
        while(!queue.isEmpty()){
            //新建一个tmp队列
            List<Integer> tmp = new ArrayList();
            //执行循环
            //循环次数：每一层的节点的个数
            for(int i = queue.size(); i>0; i--){
                //队列弹出当前节点
                TreeNode currNode = queue.poll();
                //往队列中加入当前节点的左右子节点，构建下一层
                if(currNode.left != null){
                    queue.add(currNode.left);
                }
                if(currNode.right != null){
                    queue.add(currNode.right);
                }
                //临时队列中加入当前层的节点，构建当前层节点队列，加入结果集中
                tmp.add(currNode.val);
            }
            //加入结果集
            res.add(tmp);
        }
        //返回结果集
        return res;
    }
}