103. Binary Tree Zigzag Level Order Traversal

改进版flag，在添加元素的时候加在前面，而不是用reverse整个数组。

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    List<List<Integer>> res = new LinkedList<>();
    if (root == null) return res;
    boolean flag = true;
    q.offer(root);

    while (!q.isEmpty()) {
        int levelNum = q.size();
        List<Integer> subRes = new LinkedList<>();
        for (int i = 0; i < levelNum; i++) {
            TreeNode node = q.poll();
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
            if (flag) subRes.add(node.val);
            else subRes.add(0, node.val);
        }
        flag = !flag;
        res.add(subRes);
    }
    return res;
}

原来的impl，这里最好用deque+popleft

    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        if not root: return res
        queue = [root]
        flag = False

        while queue:
            val = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
                val.append(node.val)

            if flag:
                val.reverse()
                flag = False
            else:
                flag = True
            res.append(val)
        return res