ZigZag Level Order Traversal BT

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).

Example :
Given binary tree

    3
   / \
  9  20
    /  \
   15   7

return

[
         [3],
         [20, 9],
         [15, 7]
]

Method:

Use a deque and poll elements from deque from both sides

Solution:

Time: O(n)
Space: O(n)

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {
 *      val = x;
 *      left=null;
 *      right=null;
 *     }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode A) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(A);
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> row = new ArrayList<>();
            for (int i = 0; i < size; i ++) {
                TreeNode curr = null;
                if (level % 2 == 0) {
                    curr = queue.pollFirst();
                    if (curr.left != null) queue.addLast(curr.left);
                    if (curr.right != null) queue.addLast(curr.right);
                } else {
                    curr = queue.pollLast();
                    if (curr.right != null) queue.addFirst(curr.right);
                    if (curr.left != null) queue.addFirst(curr.left);
                }
                row.add(curr.val);
            }
            result.add(row);
            level ++;
        }
        return result;
    }
}