给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

给定二叉树 [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
    
     
      > zigzagLevelOrder(TreeNode root) {        List
      
       
        > res = new ArrayList
        
         
          >(); if( root == null ) return res; Deque
          
            tree = new LinkedList<>(); tree.add( root ); TreeNode end = root; Boolean flag = true; List
           
             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指向当前层遍历的最后一个结点，如果当前层的遍历顺序是从左到右 ， 则每次弹出的都是链表的第一个元素 ， 然后再把左右结点压入链表的尾部，先压左再压右；如果当前层的遍历顺序是从右到左，则每次弹出的都是最后一个结点 ， 然后把右左压入到头部，先压右再压左。