題意

給定一個二叉樹，返回其節(jié)點值的鋸齒形層序遍歷。（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行）。

例如：
給定二叉樹 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回鋸齒形層序遍歷如下：

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

題解

利用隊列進行求解。1）每一行記錄隊列的size，然后出隊列，并把當(dāng)前節(jié)點的左右節(jié)點塞入隊列 2）利用linkedList隊列按照方向保存節(jié)點數(shù)據(jù)。

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ress = new ArrayList<>();
        if (root == null) {
            return ress;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 記錄當(dāng)前獲取到的節(jié)點
        TreeNode curNode = root;
        // 記錄方向
        boolean right = true;
        while (!queue.isEmpty()) {
            // 記錄當(dāng)前行數(shù)據(jù)size
            int size = queue.size();
            LinkedList<Integer> res = new LinkedList<>();
            // 每行數(shù)據(jù)出隊列，直到隊列全部出完
            while (size-- > 0) {
                curNode = queue.poll();  
                // 將出隊列的節(jié)點左右子節(jié)點入隊列              
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
                // 根據(jù)方向，將取出來的值塞入每行的list
                if (right) {
                    res.offerLast(curNode.val);
                } else {
                    res.offerFirst(curNode.val);
                }
            }
            right = !right;
            ress.add(res);
        }
        return ress;
    }
}