【LeetCode】103. 二叉樹的鋸齒形層序周遊

題目描述：

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

例如：

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

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

解題思路：

• 本題實際上是層序周遊的改動，層序周遊的周遊方向都是從左到右，本題是偶數層采用從左到右周遊，奇數層采用從右到左周遊；是以我們隻需要在層序周遊的基礎上增加一個leftToRight來判斷目前層是奇數層還是偶數層，偶數層的結點放到雙端對列的首位，奇數層的結點放到雙端隊列的尾部，這樣就可以實作鋸齒形層序周遊。

/**
 * 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) {
        List<List<Integer>> arr = new LinkedList<List<Integer>>();
        if (root == null) return arr;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        boolean leftToRight = true;
        while (!queue.isEmpty()) {
            Deque<Integer> deque = new LinkedList<Integer>();
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                if (leftToRight) {
                    deque.offerLast(node.val);
                } else {
                    deque.offerFirst(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            arr.add(new LinkedList<Integer>(deque));
            leftToRight = !leftToRight;
        }
        return arr;
    }
}