/*
1. bfs 按层遍历,   用双端队列
1.1 偶数层从尾部取, 奇数层从头部取
1.2 偶数从尾部放, 先左后右
1.3 奇数从头部放, 先右后左
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null ) return res;

        List<TreeNode> buffer = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);
        while (! queue.isEmpty()){
            buffer.clear();
            List<Integer> r = new ArrayList<>();
            res.add(r);
            while(!queue.isEmpty()) {
                TreeNode node = res.size() % 2 == 0 ? queue.pollLast() : queue.pollFirst();
                buffer.add(node);
                r.add(node.val);
            }

            for(int i = 0 ; i < buffer.size() ; i++){
                TreeNode cur = buffer.get(i);
                if (res.size() % 2 == 0){
                    if (cur.right != null) queue.addFirst(cur.right);
                    if (cur.left != null) queue.addFirst(cur.left);
                } else {
                    if (cur.left != null) queue.addLast(cur.left);
                    if (cur.right != null) queue.addLast(cur.right);
                }
            }
        }
        return res;
    }
}