LC 102.二叉树的层序遍历

[HealUP]

102. 二叉树的层次遍历

思路：

• 定义数组和队列：将每一层的结果保存在一个一维数组中，将每一层的一维数组保存在二维数组中 判断队列是否为空

• 遍历当前层，用size记录当前层的大小，控制当前遍历的次数

• 加入当前节点的下一层的左右孩子

• 此时又重新获取了下一层的节点的数量

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //创建一个二维数组 存放结果
        List<List<Integer>> res = new ArrayList<>();
        //创建一个队列 
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        //BFS广度优先搜索——使用队列实现
        if (root != null) {
            que.offer(root);
        };
        //广度优先搜索模板
        /*如果不为空队列不为空，就创建一个数组，记录下队列的大小，将队列中的节点的值存入数组*/
        while (!que.isEmpty()) {
            //创建数组
            List<Integer> list = new ArrayList<>();
            //记录当前层数的节点个数 即当前层的队列的大小
            int len = que.size();//队列的元素是会改变的

            while (len > 0) {//只处理len个节点
                //存放取出的节点
                TreeNode node = que.poll();
                list.add(node.val);//将节点的值放到数组中（一维数组）
                //将该节点的左右节点都放到队列中 这样就改变了队列的节点的个数了 
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
                len--;
            }
            //将该层的节点（一维数组）放到二维数组里面
            res.add(list);
        }
        return res;
    }
}