103. 二叉树的锯齿形层序遍历

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],

3<br />   / \<br />  9  20<br />    /  \<br />   15   7<br />返回锯齿形层序遍历如下：

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

层序遍历，对当前层数判断一下是奇数还是偶数就行，偶数正序，奇数翻转list再存入就可以

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        //定义一个队列用来操作节点
       Queue<TreeNode> queue = new LinkedList<>();
       List<List<Integer>> res = new ArrayList<>();
        queue.offer(root);
        //用来记录当前节点个数
        int curnum = 1;
        //记录层数
           int flag = 0;
        while(!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            int nextsum = 0;
            //用来记录下一层节点个数
            for(int i = 0; i<curnum; i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left!=null){
                    queue.offer(node.left);
                    nextsum++;
                }
                if(node.right!=null){
                    queue.offer(node.right);
                    nextsum++;
                }
            }

            if(flag%2 == 0){
                res.add(list);
            }else{
                Collections.reverse(list);
                res.add(list);
            }
                flag++;
            curnum = nextsum;
        }
        return res;
    }
}