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]

]

BFS: 用两个stack来实现层遍历

public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return res;
        }
        
        Stack<TreeNode> cur = new Stack<TreeNode>();
        Stack<TreeNode> next = new Stack<TreeNode>();
        cur.push(root);
        boolean reverse = true;
        
        while (!cur.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<Integer>();
            while (!cur.isEmpty()) {
                TreeNode node = cur.pop();
                if (reverse) {
                    if (node.left != null) {
                        next.push(node.left);
                    }
                    if (node.right != null) {
                        next.push(node.right);
                    }
                } else {
                    if (node.right != null) {
                        next.push(node.right);
                    }
                    if (node.left != null) {
                        next.push(node.left);
                    }
                }
                level.add(node.val);
            }
            reverse = !reverse;
            Stack<TreeNode> temp = cur;
            cur = next;
            next = temp;
            res.add(level);
        }
        return res;
    }
}