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

Solution:

在遍历的时候偶数层自左向右，而奇数层自右向左。在Binary Tree Level Order Traversal中我们是维护了一个队列来完成遍历，而在这里为了使每次都倒序出来，我们很容易想到用栈的结构来完成这个操作。有一个区别是这里我们需要一层一层的来处理（原来可以按队列插入就可以，因为后进来的元素不会先处理），所以会同时维护新旧两个栈，一个来读取，一个存储下一层结点。总体来说还是一次遍历完成，所以时间复杂度是O(n)，空间复杂度最坏是两层的结点，所以数量级还是O(n)（满二叉树最后一层的结点是n/2个）。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList> zigzagLevelOrder(TreeNode root) {
        ArrayList> res = new ArrayList>();
        if(root == null)
            return res;
        
        ArrayList list = new ArrayList();
        LinkedList stack = new LinkedList();
        list.add(root.val);
        res.add(list);
        stack.push(root);
        int level = 1;
        
        while(!stack.isEmpty()) {
            list = new ArrayList();
            LinkedList newStack = new LinkedList();  //for storing nodes which will be used for next level
            while(!stack.isEmpty()) {
                TreeNode node = stack.pop();
                if(level % 2 == 0) {  //偶数层从左向右
                    if(node.left != null) {
                        newStack.push(node.left);
                        list.add(node.left.val);
                    }
                    if(node.right != null) {
                        newStack.push(node.right);
                        list.add(node.right.val);
                    }
                }else {  //奇数层从右向左
                    if(node.right != null) {
                        newStack.push(node.right);
                        list.add(node.right.val);
                    }
                    if(node.left != null) {
                        newStack.push(node.left);
                        list.add(node.left.val);
                    }
                }
            }
            level++;
            if(list.size() > 0) {
                res.add(list);
            }
            stack = newStack; //assign the newStack to stack, it will be used in next loop
        }
        return res;
    }
}