[Leetcode] Binary Tree Zigzag Level 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]
]

比较Tricky的思路，按照普通的层次遍历之后，每隔一层就将结果翻转一次。但是一个问题是，这样的输出的确符合问题的要求，但是过程并不符合，这能算是正确的解法么？就比如对于一颗BST，题目要求你中序输出，但是其实你先序输出之后再排序一样能得到结果的。如果严格按照题目的要求，可以用一个变量来记录现在是从左往右还是从右往左。从左往右的话先加左子树再右子树，从右往左的话先右子树再左子树还需要再reverse一下。

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<TreeNode> level1 = new ArrayList<TreeNode>();
        List<TreeNode> level2;
        if(root == null) return result;
        level1.add(root);
        while(level1.size() != 0) {
            level2 = new ArrayList<TreeNode>();
            List<Integer> list = new ArrayList<Integer>();
            for(TreeNode node : level1) {
                list.add(node.val);
                if(node.left != null) level2.add(node.left);
                if(node.right != null) level2.add(node.right);
            }
            result.add(list);
            level1 = level2;
        }
        for(int i = 1; i < result.size(); i+=2) {
            Collections.reverse(result.get(i));
        }
        return result;
    }