# Binary Tree Zigzag Level Order Traversal ### Source - leetcode: [Binary Tree Zigzag Level Order Traversal | LeetCode OJ](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/) - lintcode: [(71) Binary Tree Zigzag Level Order Traversal](http://www.lintcode.com/en/problem/binary-tree-zigzag-level-order-traversal/) ~~~ 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). Example Given binary tree {3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] ~~~ ### 題解1 - 隊列 二叉樹的廣度優先遍歷使用隊列非常容易實現，這道題要求的是蛇形遍歷，我們可以發現奇數行的遍歷仍然可以按照廣度優先遍歷的方式實現，而對于偶數行，只要翻轉一下就好了。 ### Java ~~~ /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: A list of lists of integer include * the zigzag level order traversal of its nodes' values */ public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (root == null) return result; boolean odd = true; Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(root); while (!q.isEmpty()) { // level traversal int qLen = q.size(); ArrayList<Integer> level = new ArrayList<Integer>(); for (int i = 0; i < qLen; i++) { TreeNode node = q.poll(); level.add(node.val); if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); } // add level order reverse for even if (odd) { result.add(level); } else { Collections.reverse(level); result.add(level); } // flip odd and even odd = !odd; } return result; } } ~~~ ### 源碼分析 區分奇數偶數行使用額外變量。 ### 復雜度分析 需要 reverse 的節點數目近似為 n/2, 故時間復雜度 O(n)O(n)O(n). 最下層節點數目最多 n/2, 故reverse 操作的空間復雜度可近似為 O(n/2)O(n/2)O(n/2). 總的時間復雜度為 O(n)O(n)O(n), 空間復雜度也為 O(n)O(n)O(n). ### Reference - [Binary Tree Zigzag Level Order Traversal 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/binary-tree-zigzag-level-order-traversal/) - [Printing a Binary Tree in Zig Zag Level-Order | LeetCode](http://articles.leetcode.com/2010/09/printing-binary-tree-in-zig-zag-level_18.html)