Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree {3,9,20,#,#,15,7},

3   / \  9  20    /  \   15   7

return its zigzag level order traversal as:

[  [3],  [20,9],  [15,7]]

解题思路：

直接在上题加一条反转语句即可，JAVA实现如下：

public List
     
      
       > zigzagLevelOrder(TreeNode root) {        List
       
        
         > list = new ArrayList
         
          
           >(); if (root == null) return list; Queue
           
             queue = new LinkedList
            
             (); queue.add(root); while (queue.size() != 0) { List
             
               alist = new ArrayList
              
               (); for (TreeNode child : queue) alist.add(child.val); if(list.size()%2!=0) Collections.reverse(alist); list.add(new ArrayList
               
                (alist)); Queue
                
                  queue2 = queue; queue = new LinkedList
                 
                  (); for (TreeNode child : queue2) { if (child.left != null) queue.add(child.left); if (child.right != null) queue.add(child.right); } } return list; }