[LeetCode] Binary Tree Level Order Traversal Solution

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).


For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7




return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]



用current,last两个ArrayList<TreeNode>来保存上一层和当前层node, 


ArrayList<Integer> temp保存last里每个node的值.  用isLeft还决定是否reverse temp, 然后加入res.


 public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {


     ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();


     if (root == null)


         return res;


     boolean isLeft = true;


     ArrayList<TreeNode> last = new ArrayList<TreeNode>();





     last.add(root);


     


     while(!last.isEmpty())


     {


         ArrayList<Integer> temp = new ArrayList<Integer>();    


         ArrayList<TreeNode> current = new ArrayList<TreeNode>(); //current temp必须每次新建


         for(TreeNode node: last)


         {


             temp.add(node.val);


             if(node.left!=null)


                 current.add(node.left);


             if(node.right!=null)


                 current.add(node.right);


         }


         if(!isLeft)


             Collections.reverse(temp);


         res.add(temp);


         last = current;


         isLeft = !isLeft;             


     }


     return res;        


    }


}