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]] 思路：bfs，偶数行（i%2==1)结果reverse就可以。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public List
     
      
       > zigzagLevelOrder(TreeNode root) {        List
       
        
         > res= new ArrayList
         
          
           >(); if(root==null) { return res; } Queue
           
             check=new LinkedList
            
             (); check.offer(root); int level=0; while(!check.isEmpty()) { List
             
               curl=new ArrayList
              
               (); for(int i=check.size()-1;i>=0;i--) { TreeNode find=check.poll(); curl.add(find.val); if(find.left!=null) { check.offer(find.left); } if(find.right!=null) { check.offer(find.right); } } if(level%2!=0) { Collections.reverse(curl); } res.add(curl); level++; } return res; } }