题目：
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,#,#,15,7},
3
/ 9 20
/ 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
思路：
采用Binary Tree Level Order Traversal的方法，然后对第二行、第四行进行reverse。
package treetraversal; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class BinaryTreeZigzagLevelOrderTraversal { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<List<Integer>>(); //List<Integer> record = new ArrayList<Integer>(); levelOrderTraversal(res, root, 0); for (int i = 0; i < res.size(); ++i) { if (i % 2 == 1) { Collections.reverse(res.get(i)); } } return res; } private void levelOrderTraversal(List<List<Integer>> res, TreeNode root, int k) { if (root == null) return; if (res.size() < k + 1) { List<Integer> record = new ArrayList<Integer>(); record.add(root.val); res.add(record); } else { res.get(k).add(root.val); } levelOrderTraversal(res, root.left, k + 1); levelOrderTraversal(res, root.right, k + 1); } }
LeetCode - Binary Tree Zigzag Level Order Traversal
原文：http://www.cnblogs.com/shuaiwhu/p/5117896.html