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]
]

這題我想復(fù)雜了，想要用一個(gè)stack，一個(gè)queue分別保存當(dāng)前層和下一層的node，結(jié)果代碼寫(xiě)得很長(zhǎng)很亂，修修補(bǔ)補(bǔ)也不能AC。。

后來(lái)直接在上一題Binary Tree Level Order Traversal的代碼上加了一個(gè)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)來(lái)實(shí)現(xiàn)逆序添加。另外見(jiàn)到有人用Collections.revers來(lái)處理的。

另外leetcode solutions區(qū)有人用遞歸做的。。這是BFS啊。。對(duì)遞歸有點(diǎn)犯怵。：

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);
    }
}