自己用了两种方法写了这个二叉树层序遍历，但没想到看了看题解，又蹦出两种方法，都让我受益匪浅，具体运行时的注解全在代码里面了，刚开始看到这个题，立马想到二叉树的宽度优先遍历嘛。二话不说，直接队列走起：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>(); // 返回结果的List集合
if(root != null){
Queue<TreeNode> queue = new LinkedList<>(); //使用这个队列来宽度遍历二叉树
Map<TreeNode, Integer> map = new HashMap<>();//使用map集合，key->节点，value->节点所在的层数
queue.offer(root);//头节点入队列
map.put(root,1);//设置头节点在第一层
int curLevel = 1;//用于表示正在记录的层数
List<Integer> temp = new ArrayList<>();//用于装一层元素的容器
while(!queue.isEmpty()){//进入宽度遍历
root = queue.poll();
int curNodeLervl = map.get(root);//取出节点以及对应的节点所在层数
if(curLevel == curNodeLervl){//节点所在层数和我所记录的层数相等，则记录进容器。
temp.add(root.val);
}else{// 不相等就把上一层的节点信息结算。
result.add(temp);//把一层的容器加入总容器中
temp = new ArrayList<>();//重置容器
temp.add(root.val);//别忘了这个正在比较的节点也是要进入容器的哦
curLevel = curNodeLervl;//更新记录的层数
}
if(root.left != null){
queue.offer(root.left);
map.put(root.left, curNodeLervl +1);
}
if(root.right != null){
queue.offer(root.right);
map.put(root.right, curNodeLervl +1);
}
}
result.add(temp);
}
return result;
}
}
感觉这样子写有点复杂了，于是进行了改进，不再使用Map去记录层级信息了，代码如下：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>(); //返回结果的List集合
if(root != null){
Queue<TreeNode> queue = new LinkedList<>(); //使用这个队列来宽度遍历二叉树
queue.offer(root);//头节点入队列
TreeNode curEnd = root; //这个变量用来记录每一层的最后一个节点。
TreeNode curNext = null;//用来记录最新进队列的节点，便于后面进行条件判断的时候找到一层的最后一个节点
List<Integer> temp = new ArrayList<>();//装元素
while(!queue.isEmpty()){//宽度遍历操作
root = queue.poll();
if(root.left != null){
queue.offer(root.left);
curNext = root.left;
}
if(root.right != null){
queue.offer(root.right);
curNext = root.right;
}//在此之前都是宽度遍历的常规操作了，但是curnext把最新节点记录。
temp.add(root.val);//用来装每一层的节点们。
if(root == curEnd){//到了一层的末尾了。该结算了
result.add(temp);
temp = new ArrayList<>();
curEnd = curNext;//这个时候的curnext节点表示的值就是新一层的末尾节点啦。
}//实在没看懂别强求，拿出纸和笔推演几步就懂了。
}
}
return result;
}
}
后来呢我看到了题解一个使用二叉树的DFS，一个使用BFS，代码果然是优美的。
这个代码写的就比我自己写的优美多了，用先序遍历做深度优先遍历，每一层用一个deep巧妙的解决了。赞。
来看代码：
class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
check01(root, 0);
return result;
}
public void check01(TreeNode root, int deep){
if(root == null) return;
deep++;
if(result.size() < deep){
List<Integer> temp = new ArrayList<>();
result.add(temp);
}
result.get(deep -1).add(root.val);
check01(root.left, deep);
check01(root.right, deep);
}
}
接下来就是和我一样的宽度优先遍历的思想了，但是它直接用一个len变量解决了记录层数的问题。赞。
来看代码：
class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
check02(root);
return result;
}
public void check02(TreeNode root){
if(root != null){
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int len = queue.size();
List<Integer> temp = new ArrayList<>();
while(len != 0){
root = queue.poll();
temp.add(root.val);
if(root.left != null) queue.offer(root.left);
if(root.right != null) queue.offer(root.right);
--len;
}
result.add(temp);
}
}
}
}
感谢大佬的指引：代码随想录，马士兵左神。
