一共三道要求不同的打印方式的从上到下打印二叉树
第一道：
/从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。/
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
提示：
节点总数 <= 1000
思路：
这道题本质就是二叉树的层序遍历，直接撸
class Solution {
public int[] levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> list = new ArrayList<>();
if(root != null)
queue.offer(root);
while(queue.size() != 0){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null)
queue.offer(node.left);
if(node.right != null)
queue.offer(node.right);
}
// 将结果转为 int[]
int[] result = new int[list.size()];
int index = 0;
for(Integer i : list)
result[index ++] = i;
return result;
}
}
第二道：
/从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。/
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
提示：
节点总数 <= 1000
思路：
层序打印的同时，维护两个变量 cur（当前层的数量）、next（下一层的数量）。
每次队列 poll 出一个节点时，cur 减一，如果该结点存在孩子节点，则 next 加上孩子节点的数量（下一层的数量）。当 cur == 0 时，即当前层数的节点打印完，开始下一层的打印 cur = next。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
ArrayList<List<Integer>> result = new ArrayList();
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> line = new ArrayList<>();
int cur = 0, next = 0; // 当前层的数量，下一层的数量
if(root != null)
queue.offer(root);
cur = 1;
while(queue.size() != 0){
TreeNode node = queue.poll();
line.add(node.val);
if(node.left != null){
queue.offer(node.left);
next ++;
}
if(node.right != null){
queue.offer(node.right);
next ++;
}
// 当前层数打印完，开始打印下一层。
if(--cur == 0){
result.add(line);
line = new ArrayList<>();
cur = next;
next = 0;
}
}
if(line.size() != 0)
result.add(line);
return result;
}
}
第三道
/请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。/
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
解答：
利用双栈 left （出栈的顺序等于该层次从左到右打印的顺序），right（出栈的顺序等于该层次从右到左打印的顺序）， 同时利用一个 boolean 类型 turn 来控制遍历的方式，turn = true时：从左到右打印，turn = false 时，从右到左打印。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> line = new ArrayList<>();
Stack<TreeNode> left = new Stack<>();
Stack<TreeNode> right = new Stack<>();
boolean turn = true; //true:左到右遍历， false 反之
if(root != null)
left.push(root);
while(left.size()!=0 || right.size()!=0){
TreeNode node = turn? left.pop() : right.pop();
line.add(node.val);
// 从左开始遍历与从右开始遍历，入对应的栈的顺序不同
if(turn){
if(node.left != null)
right.push(node.left);
if(node.right != null)
right.push(node.right);
}else{
if(node.right != null)
left.push(node.right);
if(node.left != null)
left.push(node.left);
}
// 控制下一层的转向
if(turn && left.isEmpty()){
turn = false;
result.add(line);
line = new ArrayList<>();
}else if(!turn && right.isEmpty()){
turn = true;
result.add(line);
line = new ArrayList<>();
}
}
if(line.size() != 0)
result.add(line);
return result;
}
}
利用队列解决，
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
if(res.size() % 2 == 1) Collections.reverse(tmp);
res.add(tmp);
}
return res;
}
}
