剑指 Offer 32 - II. 从上到下打印二叉树 II
Offer_32
题目描述：
题解分析：
这道题我一开始想到的解决方法较粗暴，就是使用两个变量来记录当前层的节点数和下一层的结点数。
以上的方法虽然可行，但是较复杂。实际每次队列里存储的就是当前层的所有结点，利用这个性质可以较快解题。
解法一：
package com.walegarrett.offer;
/**
* @Author WaleGarrett
* @Date 2021/2/1 14:50
*/
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 题目：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
* 解析：使用队列按照层次打印层次遍历序列
*/
public class Offer_32_2 {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null)
return new ArrayList<List<Integer>>();
List<List<Integer>> list = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
int currentLayerNum = 1;
int nextLayerNum = 0;
int cnt = 0;
List<Integer> current = new ArrayList<>();
while(!que.isEmpty()){
TreeNode temp = que.peek();
que.poll();
current.add(temp.val);
cnt++;
if(temp.left != null) {
que.offer(temp.left);
nextLayerNum++;
}
if(temp.right != null) {
que.offer(temp.right);
nextLayerNum++;
}
if(cnt == currentLayerNum){//当前层已经遍历结束
currentLayerNum = nextLayerNum;
nextLayerNum = 0;
cnt = 0;
list.add(current);
current = new ArrayList<>();//注意这里不能使用current.clear，否则所有的队列都将为空
}
}
return list;
}
}
解法二：
class Offer_32_2_1 {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null)
return new ArrayList<List<Integer>>();
List<List<Integer>> list = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
while(!que.isEmpty()){
List<Integer> current = new ArrayList<>();
for(int i = que.size(); i> 0; i--){
TreeNode temp = que.peek();
que.poll();
current.add(temp.val);
if(temp.left != null) {
que.offer(temp.left);
}
if(temp.right != null) {
que.offer(temp.right);
}
}
list.add(current);
}
return list;
}
}
