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).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

这题我想复杂了，想要用一个stack，一个queue分别保存当前层和下一层的node，结果代码写得很长很乱，修修补补也不能AC。。

后来直接在上一题Binary Tree Level Order Traversal的代码上加了一个flag判断就轻松AC了。

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int curNum = 1;
        int nextNum = 0;
        List<Integer> cell = new ArrayList<>();
        boolean flag = true;
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            curNum--;
            //flag为true就正向插入
            if (flag) {
                cell.add(temp.val);
            } else {
                cell.add(0, temp.val);
            }

            if (temp.left != null) {
                queue.add(temp.left);
                nextNum++;
            }
            if (temp.right != null) {
                queue.add(temp.right);
                nextNum++;
            }
            if (curNum == 0) {
                res.add(cell);
                curNum = nextNum;
                nextNum = 0;
                flag = !flag;
                cell = new ArrayList<>();
            }
        }
        return res;
    }

这里直接用add(index,num)来实现逆序添加。另外见到有人用Collections.revers来处理的。

另外leetcode solutions区有人用递归做的。。这是BFS啊。。对递归有点犯怵。：

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) 
    {
        List<List<Integer>> sol = new ArrayList<>();
        travel(root, sol, 0);
        return sol;
    }
    
    private void travel(TreeNode curr, List<List<Integer>> sol, int level)
    {
        if(curr == null) return;
        
        if(sol.size() <= level)
        {
            List<Integer> newLevel = new LinkedList<>();
            sol.add(newLevel);
        }
        
        List<Integer> collection  = sol.get(level);
        if(level % 2 == 0) collection.add(curr.val);
        else collection.add(0, curr.val);
        
        travel(curr.left, sol, level + 1);
        travel(curr.right, sol, level + 1);
    }
}