二叉树的锯齿形层序遍历
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下：
[
[3],
[20,9],
[15,7]
]
思路：
依然使用队列，不过要用双端队列了，每一层出队列和添加新元素进入队列的顺序都和上一层相反，用一个标志表示即可。
代码:
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<>();
Deque<TreeNode> deque =new ArrayDeque<>();
//这个表示队列中当前层的节点是否从下面出双端队列
boolean isDown =true;
if(root==null){return res;}
deque.add(root);
while(deque.size()!=0){
List<Integer> list=new ArrayList<>();
int num=deque.size();
if(isDown){
for(int i=0;i<num;i++){
TreeNode node=deque.pollLast();
list.add(node.val);
if(node.left!=null){deque.addFirst(node.left);}
if(node.right!=null) {deque.addFirst(node.right); }
}
}
else{
for(int i=0;i<num;i++){
TreeNode node=deque.pollFirst();
list.add(node.val);
if(node.right!=null) {deque.addLast(node.right); }
if(node.left!=null){deque.addLast(node.left);}
}
}
res.add(list);
isDown=!isDown;
}
return res;
}
}
