# 0103. Binary Tree Zigzag Level Order Traversal
###### tags: `Leetcode` `Medium` `FaceBook` `BFS`
Link: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
## 思路
层序遍历

如果需要从左往右，则按照正常顺序遍历，如果需要从右往左，则是用linkedlist里面的addFirst函数，可以让时间复杂度变成O(1)，**如果用arraylist里面的```l.add(0, curr.val)```时间复杂度是O(N)**

**第10行声明的时候一定要声明成```LinkedList<Integer> l```而不是```List<Integer> l```，list里面没有addFirst函数**
## Code

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root==null) return ans;
        boolean left = true;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int size = q.size();
            LinkedList<Integer> l = new LinkedList<>();
            for(int i = 0;i < size;i++){
                TreeNode curr =  q.poll();
                if(curr.left!=null) q.add(curr.left);
                if(curr.right!=null) q.add(curr.right);
                if(left) l.add(curr.val);
                else l.addFirst(curr.val);
            }
            left = !left;
            ans.add(l);
        }
        return ans;
    }
}