Binary Tree Zigzag Level Order T

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

答案

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null) return new ArrayList<List<Integer>>(); ;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        q.offer(root);
        boolean dir = true;
        while(q.size() != 0) {
            int curr_size = q.size();
            List<Integer> temp = new ArrayList<Integer>();
            for(int i = 0; i < curr_size; i++) {
                TreeNode t = q.poll();
                if(dir) temp.add(t.val);
                else temp.add(0, t.val);
                if(t.left != null) q.offer(t.left);
                if(t.right != null) q.offer(t.right);
            }
            lists.add(temp);
            dir = !dir;
        }
        return lists;       
    }
}

以上答案中有一个小细节，如果改正之后performance能提高10倍

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null) return new ArrayList<List<Integer>>(); ;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        q.offer(root);
        boolean dir = true;
        while(q.size() != 0) {
            int curr_size = q.size();
            List<Integer> temp = Arrays.asList(new Integer[curr_size]);

            for(int i = 0; i < curr_size; i++) {
                TreeNode t = q.poll();
                if(dir) temp.set(i, t.val);
                else temp.set(curr_size - i - 1, t.val);
                if(t.left != null) q.offer(t.left);
                if(t.right != null) q.offer(t.right);
            }
            lists.add(temp);
            dir = !dir;
        }
        return lists;       
    }
}