【刷爆力扣之二叉树】102. 二叉树的层序遍历

102. 二叉树的层序遍历

二叉树的层序遍历需要队列数据结构，还需要记录每一层节点的个数，可以定义一个变量记录，也可以直接使用队列中元素个数表示每一层的节点个数，每次获取队列头中的节点后，需要判断该节点是否有左右孩子，如果有，则放入队列，并且将记录每一层节点个数的变量加一。

// 二叉树的层序遍历-变量记录每层节点个数
public List<List<Integer>> levelOrder(TreeNode root) {
    // 存储结果
    List<List<Integer>> result = new ArrayList<>();
    // 如果根节点为空，则直接返回结果
    if (root == null) {
        return result;
    }
    // 创建一个队列
    Queue<TreeNode> queue = new LinkedList<>();
    // 将根节点放入队列
    queue.offer(root);
    // 记录每一层的节点个数
    int c1 = 1;//每一层节点个数
    // 当队列不为空时
    while (!queue.isEmpty()) {
        // 记录下一层节点个数
        int c2 = 0;//下一层节点个数
        // 创建一个存储每一层节点的列表
        List<Integer> lever = new ArrayList<>();
        // 遍历每一层节点
        for (int i = 0; i < c1; i++) {
    
            // 从队列中取出一个节点
            TreeNode node = queue.poll();
            // 将节点的值添加到列表中
            lever.add(node.val);
            // 如果该节点有左子节点，则将左子节点放入队列
            if (node.left != null) {
                queue.offer(node.left);
                c2++;
            }
            // 如果该节点有右子节点，则将右子节点放入队列
            if (node.right != null) {
                queue.offer(node.right);
                c2++;
            }
        }
        // 更新每一层节点个数
        c1 = c2;
        // 将每一层节点列表添加到结果中
        result.add(lever);
    }
    // 返回结果
    return result;
}

//二叉树的层序遍历-直接使用队列长度表示每层节点个数
public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return result;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            // 直接使用队列的长度表示每一层节点的个数
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode polled = queue.poll();
                level.add(polled.val);
                // 如果有左右孩子，则加入队列
                if(polled.left!=null){
                    queue.offer(polled.left);
                }
                if(polled.right!=null){
                    queue.offer(polled.right);
                }
            }
            result.add(level);
        }
        return result;
    }

之所以可以使用队列长度直接表示每层节点个数是因为，从根节点开始，节点个数为1，这是已知的，在遍历当前层时，将当前层的节点全部弹出，又把下一层的节点全部入队，因此，只要遍历到下一层（当前层有孩子），那么说明此时的队列中的长度就是当前层的节点个数（即没有上一层节点，又没有下一层节点）。