102. 二叉树的层序遍历 - 示意图

15

7

8

结果数组：[[3]]

1) 第一次循环：3出队，加入子数组中，并将其左右子节点入队

20

3

结果数组：

3) 第三次循环：    ① 8出队，加入子数组中，左右子节点为空，不入队列    ② 15出队，加入子数组中，同上    ③ 7出队，加入子数组中，同上

9

102. 二叉树的层序遍历https://leetcode-cn.com/problems/binary-tree-level-order-traversal/【解法】：使用广度优先搜索，时间复杂度O(n)，空间复杂度O(1)     【算法思路】：通过队列存储每一层的数据，当队列不为空的时候，每次循环中都将队列中的数据poll()出来，并且加入到子数组中。并将每次poll()出来的节点node的左右子节点分别入队【示例代码】：public List<List<Integer>> levelOrder(TreeNode root) {        // 1. 确定入参和返回值        List<List<Integer>> res = new ArrayList<>();                // 2. 确定终止条件        if (null == root) return res;        // 3. 处理单层逻辑（我们这里使用队列的“先进先出”特性来存储每一层的数据）        Queue<TreeNode> queue = new LinkedList<>();        queue.offer(root);        while ( !queue.isEmpty()) {            // 每次循环，队列中都记录“一层的数据”            int size = queue.size();            List<Integer> subList = new ArrayList<>();            for (int i=0; i<size; ++i) {                TreeNode node = queue.poll();                subList.add(node.val);                                // 将 当前出队节点的 左右子节点，分别入队                if (null != node.left) queue.offer(node.left);                if (null != node.right) queue.offer(node.right);            }            res.add(subList);        }        // 队列为空，则所有的都遍历完了        return res;    }

4) 队列为空，退出循环

2) 第二次循环：    ① 9出队，加入子数组中，并将其左右子节点 8入队    ② 20出队，加入子数组中，并将其左右子节点 15、7入队