102.二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
本题是要层级遍历二叉树，将每层的所有节点都存入到list中。主要存在两个需要解决的点。
- 如何层级遍历二叉树
- 如何知道每层有哪些节点
接替围绕着这两个点，首先可以使用队列来层级遍历每个节点，思路类似于宽度优先搜索（bfs），先将root节点放入队列中，每次都弹出队头节点，取出节点，然后将取出节点的left节点和right节点依次放入到队列中，直到没有节点再能放入到队列中为止（即：队列为空）。
随后再此基础上，创建变量lastNode表示为当前层的最后一个节点，nextLastNode表示为下一层的最后一个节点，这个变量每次从队列中取出节点都会进行更新，当弹出节点等于lastNode时，即可将一层的list存入总的list，且将lastNode更新为nextLastNode。
代码实现如下：
public static List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
TreeNode lastNode = root;
TreeNode nextLastNode = null;
Queue<TreeNode> queue = new ArrayDeque<>();
List<Integer> list = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
nextLastNode = node.left;
queue.add(node.left);
}
if (node.right != null) {
nextLastNode = node.right;
queue.add(node.right);
}
if (lastNode == node) {
res.add(list);
list = new ArrayList<>();
lastNode = nextLastNode;
}
}
return res;
}
