1.问题

给你二叉树的根节点 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

2.解题思路

2.1 队列

二叉树每层的遍历符合队列的特性，必须FIFO(first in first out)，再遍历每层完成后，可以给定一个标记或者层数，表示该层已经遍历完毕，可以将此时的该层遍历结果输出。伪代码：

//定义队列
Queue q;
//结果集
List res;
//root 入队
q.add(root);
//给定一个标识，标记第一层遍历的结尾
q.add(null);
while(q不为空){//出队temp=q.peek();//不是标识的话，入队root.left、root.rightif(temp不为null){res.add(temp.val);if(temp.left不为null){q.add(temp.left);}if(temp.right不为null){q.add(temp.right);}}//否则，该层遍历完毕else {q.add(null);}
}

复杂度分析：

• 时间复杂度：O(n)，其中n为二叉树的节点数，每个节点访问一次
• 空间复杂度：O(n)，队列的空间为二叉树的一层的节点数，最坏情况二叉树的一层为O(n)级

2.2 递归

根据二叉树的定义，不难看出，每个节点都有类似的性质。当遍历发生时，对于其左右子树同样适用相同的规则，非常适合递归。可以借鉴之前对于二叉树的前中后序遍历，既然可以用递归解决，那层次遍历也未尝不可。同样可以运用标记的思想，对于同一层，可以标记为相同的深度来进行遍历。伪代码：

void traverse(TreeNode root, int depth);//计入子节点，则深度depth+1
//递归左右时深度记得加1
traverse(root.left, depth + 1); 
traverse(root.right, depth + 1);//每个节点值放入对应的二维数组相应行
res[depth - 1].push_back(root->val);

复杂度分析

• 时间复杂度：O(n)，n为节点数量，DFS对每个节点访问一次，因此递归调用n次，每次调用执行常数次操作，时间复杂度O(n)。
• 空间复杂度：O(n)，空间复杂度在于递归调用深度和每次递归调用辅助空间，辅助空间为常数级，与节点深度相关，当节点深度为n时最大，为O(n)。

3.代码

import java.util.*;/ public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;* }*/public class Solution {/* 利用队列的性质* @param root TreeNode类* @return int整型ArrayList<ArrayList<>>*/public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {if (null == root) {return new ArrayList<>();}//结果ArrayList<ArrayList<Integer>> res = new ArrayList<>();//每层临时结果ArrayList<Integer> temp = new ArrayList<>();TreeNode node;//队列LinkedList<TreeNode> list = new LinkedList<TreeNode>();list.add(root);//给定个 层标识list.add(null);//遍历队列while (!list.isEmpty()) {node = list.removeFirst();if (null != node) {temp.add(node.val);if (null != node.left) {list.add(node.left);}if (null != node.right) {list.add(node.right);}}//为null节点，说明这一层已经遍历完成else {//这里一定要判断下，如果为空，表明二叉树已经遍历完成了if (!temp.isEmpty()) {res.add(temp);temp = new ArrayList<>();list.add(null);}}}return res;}//记录输出ArrayList<ArrayList<Integer> > res = new ArrayList();//递归public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {if(root == null)//如果是空，则直接返回return res;//递归层次遍历traverse(root, 0);return res;}//临时结果集ArrayList<Integer> row;void traverse(TreeNode root, int depth) {if(root != null){//新的一层: 对于二维res来说，将根视为第0层，树的深度正好等于一维res的个数if(res.size() == depth){ row = new ArrayList();res.add(row);//读取该层的一维数组，将元素加入末尾}else{row = res.get(depth); }row.add(root.val);}elsereturn;//递归左右时深度记得加1traverse(root.left, depth + 1);traverse(root.right, depth + 1);}
}