Binary Tree Zigzag Level Order Traversal

BFS
 1 public class Solution {
 2     public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         LinkedList<TreeNode> visiting = new LinkedList<TreeNode>();
 6         LinkedList<TreeNode> next = new LinkedList<TreeNode>();
 7         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 8         
 9         if(root == null)
10             return result;
11         int level = 0;
12         visiting.add(root);
13         while(!visiting.isEmpty()){
14             ArrayList<Integer> now = new ArrayList<Integer>();
15             while(!visiting.isEmpty()){
16                 TreeNode tmp = visiting.poll();
17                 now.add(tmp.val);
18                 if(tmp.left!=null)
19                     next.add(tmp.left);
20                 if(tmp.right!=null)
21                     next.add(tmp.right);
22             }
23             
24             if(level%2 == 1){
25                 int start = 0;
26                 int end = now.size()-1;
27                 while(start < end){
28                     int tmp = now.get(start);
29                     now.set(start, now.get(end));
30                     now.set(end, tmp);
31                     start++;
32                     end--;
33                 }
34             }
35             
36             result.add(now);
37             visiting.addAll(next);
38             next.clear();
39             level++;
40         }
41         return result;
42         
43     }
44 }