LeetCoder - 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]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

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

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

        if(root==null) {

            return ret;

        }

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

        lst.add(root);

        boolean reverse = false;

        while(lst.size()!=0) {

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

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

            for(TreeNode node : lst) {

                level.add(node.val);

                if(node.left!=null) tmp.add(node.left);

                if(node.right!=null) tmp.add(node.right);

            }

            if(reverse) {

                Collections.reverse(level);

            }

            ret.add(level);

            reverse = !reverse;

            lst = tmp;

        }

        return ret;

    }

}