问题描述：

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,null,null,15,7],

3   / \  9  20    /  \   15   7

 

return its zigzag level order traversal as:

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

算法分析：和前面问题类似。

public class BinaryTreeZigzagLevelOrderTraversal {	 public List
     
      
       > zigzagLevelOrder(TreeNode root) 	 {		 List
       
         list = new ArrayList<>();		 List
        
         
          > res = new ArrayList<>();		 		 if(root == null) 		 {			 return res;		 }		 		 Stack
          
            s1 = new Stack<>(); Stack
           
             s2 = new Stack<>(); s1.push(root); while(!s1.isEmpty() || !s2.isEmpty()) { while(!s1.isEmpty()) { TreeNode temp = s1.pop(); if(temp.left != null) { s2.push(temp.left); } if(temp.right != null) { s2.push(temp.right); } list.add(temp.val); } if(list.size() != 0) res.add(list); list = new ArrayList<>(); while(!s2.isEmpty()) { TreeNode temp = s2.pop(); if(temp.right != null) { s1.push(temp.right); } if(temp.left != null) { s1.push(temp.left); } list.add(temp.val); } if(list.size() != 0) res.add(list); list = new ArrayList<>(); } return res; }}