题目描述
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
样例
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下:
[
[3],
[20,9],
[15,7]
]
算法1
(BFS) $O(n)$
这题其实就是利用BFS 打印树的节点值的升级版。所以我们只需要加多一个标志位: flag ,当true 的时候,每一层的节点按照原来的顺序。当进入到下一层的遍历时,flag = !flag,此时该层的节点就得反向输出,这里就要借助数据结构:双端队列,可以从队头,队尾插入数据。
时间复杂度
每个节点遍历一次,O(N)
参考文献
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if(root == null) return new LinkedList();
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new LinkedList<>();
boolean flag = true;
queue.add(root);
while(!queue.isEmpty()){
Deque<Integer> deque = new LinkedList<>();
int n = queue.size(); //queue.size() 一定要单独写出来,不能写在for 循环中,因为for 循环中我们会不断地往
//queue 中加入值,那么queue.size() 就会进行动态增加
for(int i = 0; i < n; i++){
TreeNode poll = queue.poll();
if(flag){
deque.offerLast(poll.val);
}else{
deque.offerFirst(poll.val);
}
if(poll.left != null){
queue.add(poll.left);
}
if(poll.right != null){
queue.add(poll.right);
}
}
res.add(new LinkedList(deque));
flag = !flag;
}
return res;
}
}