優質博文：IT-BLOG-CN

一、題目

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

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[20,9],[15,7]]

示例 2：
輸入：root = [1]
輸出：[[1]]

示例 3：
輸入：root = []
輸出：[]

樹中節點數目在范圍[0, 2000]內
-100 <= Node.val <= 100

二、代碼

廣度優先遍歷： 規定二叉樹的根節點為第0層，如果當前層數是偶數，從左至右輸出當前層的節點值，否則，從右至左輸出當前層的節點值。我們依然可以沿用第102題的思想，修改廣度優先搜索，對樹進行逐層遍歷，用隊列維護當前層的所有元素，當隊列不為空的時候，求得當前隊列的長度 size，每次從隊列中取出size個元素進行拓展，然后進行下一次迭代。

為了滿足題目要求的返回值為「先從左往右，再從右往左」交替輸出的鋸齒形，我們可以利用「雙端隊列」的數據結構來維護當前層節點值輸出的順序。

雙端隊列是一個可以在隊列任意一端插入元素的隊列。在廣度優先搜索遍歷當前層節點拓展下一層節點的時候我們仍然從左往右按順序拓展，但是對當前層節點的存儲我們維護一個變量isOrderLeft記錄是從左至右還是從右至左的：
【1】如果從左至右，我們每次將被遍歷到的元素插入至雙端隊列的末尾。
【2】如果從右至左，我們每次將被遍歷到的元素插入至雙端隊列的頭部。

當遍歷結束的時候我們就得到了答案數組。

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new LinkedList<List<Integer>>();if (root == null) {return ans;}Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();nodeQueue.offer(root);boolean isOrderLeft = true;while (!nodeQueue.isEmpty()) {Deque<Integer> levelList = new LinkedList<Integer>();int size = nodeQueue.size();for (int i = 0; i < size; ++i) {TreeNode curNode = nodeQueue.poll();if (isOrderLeft) {levelList.offerLast(curNode.val);} else {levelList.offerFirst(curNode.val);}if (curNode.left != null) {nodeQueue.offer(curNode.left);}if (curNode.right != null) {nodeQueue.offer(curNode.right);}}ans.add(new LinkedList<Integer>(levelList));isOrderLeft = !isOrderLeft;}return ans;}
}

時間復雜度： 其中N為二叉樹的節點數。每個節點會且僅會被遍歷一次。
空間復雜度： O(N)。我們需要維護存儲節點的隊列和存儲節點值的雙端隊列，空間復雜度為O(N)。