Binary Tree Zigzag Level Order — Alternating Direction BFS

# Python
from collections import deque
def zigzagLevelOrder(root):
    if not root: return []
    queue = deque([root]); result = []; left_to_right = True
    while queue:
        level = deque()
        for _ in range(len(queue)):
            node = queue.popleft()
            if left_to_right: level.append(node.val)
            else: level.appendleft(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(list(level))
        left_to_right = not left_to_right
    return result

// Java
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res=new ArrayList<>();
    if (root==null) return res;
    Queue<TreeNode> q=new LinkedList<>(); q.offer(root); boolean ltr=true;
    while (!q.isEmpty()) {
        int sz=q.size(); Deque<Integer> level=new ArrayDeque<>();
        while (sz-->0) {
            TreeNode n=q.poll();
            if(ltr) level.addLast(n.val); else level.addFirst(n.val);
            if(n.left!=null) q.offer(n.left);
            if(n.right!=null) q.offer(n.right);
        }
        res.add(new ArrayList<>(level)); ltr=!ltr;
    }
    return res;
}