[Leetcode 103]二叉树zigzag交叉遍历Binary Tree Zigzag Level Order Traversal

class Solution {
 public List> zigzagLevelOrder(TreeNode root) {
        List> ans=new ArrayList<>();
        if(root==null)
            return ans;

        Queue q=new LinkedList();
        q.add(root);

        int level=0; //zigzag新加

        while(!q.isEmpty()){
            int size=q.size();
            List tmp=new ArrayList<>();
            for(int i=0;i){
                TreeNode curNode=q.remove();
                tmp.add(curNode.val);

                if(curNode.left!=null){
                    q.add(curNode.left);
                }
                if(curNode.right!=null){
                    q.add(curNode.right);
                }
            }
            //zigzag新加
            if(level%2==1){
                Collections.reverse(tmp);
            }
            level++;

            ans.add(tmp);
        }
        return ans;
    }