Binary Tree ZigZag Order Traversal

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语言: BinaryTreeZigZag

01 public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
03     if(root==null)
04         return results;
05     ArrayList<TreeNode> trees=new ArrayList<TreeNode>();
06     ArrayList<Integer> depth=new ArrayList<Integer>();
07     trees.add(root);
08     depth.add(1);
09     ArrayList<Integer> level1=new ArrayList<Integer>();
10     level1.add(root.val);
11     results.add(level1);
12     while(!trees.isEmpty())
13     {
14         TreeNode parent=trees.remove(0);
15         int curr_level=depth.remove(0);
16         if(parent.left!=null)
17         {
18             trees.add(parent.left);
19             depth.add(curr_level+1);
20         }
21         if(parent.right!=null)
22         {
23             trees.add(parent.right);
24             depth.add(curr_level+1);
25         }
26         int size=depth.size();
27         if(size>0 && depth.get(0)==depth.get(size-1) && curr_level==depth.get(0)-1)
28         {
29             ArrayList<Integer> treelevel=new ArrayList<Integer>();
30             if(depth.get(0)%2==1)
31             {
32                 for(int i=0;i<trees.size();i++)
33                 {
34                     treelevel.add(trees.get(i).val);
35                 }
36             }
37             else
38             {
39                 for(int i=0;i<trees.size();i++)
40                 {
41                     treelevel.add(0,trees.get(i).val);
42                 }
43             }
44             results.add(treelevel);
45         }
46     }
47   
48     return results;
49 
50 }