103. Binary Tree Zigzag Level Order Traversal

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

BFS搜索，每次遍历挤出整层的节点。
根据真值reverse来判断列表顺序。
当reverse为真，则每次添加元素到列表头。
反之则添加元素到列表尾。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Deque<TreeNode> q = new LinkedList<>();
        q.add(root);
        int size = 1;
        boolean reverse = false;
        
        while(!q.isEmpty()){
            List<Integer> level = new ArrayList<Integer>();
            for(int i = 0; i < size; i++){
                TreeNode curr = q.poll();
                if(reverse){
                    level.add(0, curr.val);
                } 
                else{
                    level.add(curr.val);
                } 
                if(curr.left != null) q.add(curr.left);
                if(curr.right != null) q.add(curr.right);
                    
            }

            reverse = !reverse;
            ret.add(level);
            size = q.size();
        }
        return ret;
    }
}

双端队列，根据真值reverse来判断是取队头还是取队尾。
每层级需要遍历所有的节点。
注意添加节点时也需要根据reverse来决定加入对头还是队尾。
（从一个层级取出时，加入下一个层级元素需要从队列另一边压入。）
同时左右节点的加入顺序也需要调整。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Deque<TreeNode> dq = new LinkedList<>();
        dq.add(root);
        int size = 1;
        boolean reverse = false;
        
        while(!dq.isEmpty()){
            List<Integer> temp = new ArrayList<Integer>();
            for(int i = 0; i < size; i++){
                if(reverse){
                    TreeNode curr = dq.removeLast();
                    if(curr.right != null) dq.offerFirst(curr.right);
                    if(curr.left != null) dq.offerFirst(curr.left);
                    temp.add(curr.val);
                } 
                else{
                    TreeNode curr = dq.removeFirst();
                    if(curr.left != null) dq.offerLast(curr.left);
                    if(curr.right != null) dq.offerLast(curr.right);
                    temp.add(curr.val);
                } 
            }

            reverse = !reverse;
            ret.add(temp);
            size = dq.size();
        }
        return ret;
    }
}