在面试中遇到了这道题，没上手写过答起来也是费劲，哎，真的是熟能生巧啊。
此题分为I，II，III，三道题，第一道题就是简单的层次遍历，后面两道是第一道题的衍生题，这个题倒是蛮适合做为面试题的。
I - 简单
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
解题思路
二叉树的层次遍历，也就是广度优先遍历，只要用对辅助空间就很好解决，层次遍历很明显是先进先出，所以选队列就是没有错了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> treeLevel = new ArrayList();
if(root == null)
return new int[]{};
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
treeLevel.add(node.val);
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
int[] arr = new int[treeLevel.size()];
for(int i=0; i<treeLevel.size();i++){
arr[i] = treeLevel.get(i);
}
return arr;
}
}
让我们来注意几个点：
- Queue 只是接口，需要实现，因为我敲代码的时候没有用IDE，我说我要用LinkedList，他居然说直接用queue就可以了，真是汗😓。
- Queue的remove()和poll()还有add()和offer()的区别就是前者会抛异常，后面只会返回false。
- 遍历出来的node也要放在辅助的ArrayList里面
II. - 按每层打印 -中等 面试真题
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
解题思路
LeetCode 比较好，至少给了返回参数类型 List<List<Integer>>。 层次打印，无外乎就是每层放到一个List里面再汇总。面试的时候想到出队的节点再放到List里，但怎么也想不明白怎么循环了，卡住了，至少需要双层循环，但怎么循环才能让入队的子节点不算进来呢？思路就是从后向前循环，这个时候queue的长度还不包含出队的节点的子节点。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root == null)
return res;
queue.add(root);
while(!queue.isEmpty()){
List<Integer> tmp = new ArrayList();
//从高向低循环是为了不遍历，新添加的子节点，
//这个i是指一个count，没有index的作用
for(int i = queue.size(); i>0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
res.add(tmp);
}
return res;
}
}
III. 之字形打印 - 中等
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
解题思路
这个题又是上一个题的衍生题，之字形就是从前向后下一层再从过后向前，思路就是维护一个双向队列，奇数层从前出队，偶数层从后出队。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Deque<TreeNode> queue = new ArrayDeque<>();
List<List<Integer>> res = new ArrayList<>();
int level = 0;
if(root == null)
return res;
queue.addFirst(root);
while(!queue.isEmpty()){
List<Integer> tmp = new ArrayList<>();
for(int i=queue.size(); i>0;i--){
TreeNode node = (level%2==0)?queue.pollFirst():queue.pollLast();
tmp.add(node.val);
if(level%2==0){
if(node.left != null) queue.addLast(node.left);
if(node.right != null) queue.addLast(node.right);
}else{
if(node.right != null) queue.addFirst(node.right);
if(node.left != null) queue.addFirst(node.left);
}
}
level++;
res.add(tmp);
}
return res;
}
}
注意
- pollFirst() 和 addLast() 成对
- 偶数层先add左孩子，奇数层先add右孩子
- 第二层循环都是从后向前，避免循环新加的孩子节点
网友评论