给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
复制代码返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
复制代码/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if( root == null ) return res;
Deque<TreeNode> tree = new LinkedList<>();
tree.add( root );
TreeNode end = root;
Boolean flag = true;
List<Integer> list = new ArrayList<>();
while( !tree.isEmpty() ){
TreeNode cur = flag ? tree.pollFirst() : tree.pollLast();
list.add( cur.val );
if( flag ){
if( cur.left != null ){
tree.offerLast( cur.left );
}
if( cur.right != null ){
tree.offerLast( cur.right );
}
}else{
if( cur.right != null ){
tree.offerFirst( cur.right );
}
if( cur.left != null ){
tree.offerFirst( cur.left );
}
}
if( cur == end ){
res.add( list );
list = new ArrayList<>();
end = flag ? tree.peekFirst() : tree.peekLast();
flag = !flag;
}
}
return res;
}
}
复制代码解题思路： 使用双向链表保存下一层的值 ， 用end指向当前层遍历的最后一个结点，如果当前层的遍历顺序是从左到右 ， 则每次弹出的都是链表的第一个元素 ， 然后再把左右结点压入链表的尾部，先压左再压右；如果当前层的遍历顺序是从右到左，则每次弹出的都是最后一个结点 ， 然后把右左压入到头部，先压右再压左。