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).
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] ]
SOLUTION :
这题跟level order的模版都是一样的，用queue进行BFS，只不过中间要加一些约束条件，调整level list里面结果的顺序。一般来说碰到类似奇偶循环的约束条件，就判断一下(n % 2 ＝＝ 0)。很简单的小技巧，记住就好。
具体看代码，备注调整位置：
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;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int n = 0;// 增加进行判断的参数
while (!queue.isEmpty()){
ArrayList<Integer> list = new ArrayList<Integer>();
int size = queue.size();
for (int i = 0; i < size; i++){
TreeNode cur = queue.remove();
//这里进行list.add的约束
if (n % 2 == 0){
list.add(cur.val);
} else {
list.add(0, cur.val);
}
if (cur.left != null){
queue.offer(cur.left);
}
if (cur.right != null){
queue.offer(cur.right);
}
}
n++;// 以及这里
result.add(list);
}
return result;
}
}
[Lintcode]Binary Tree Zigzag Level Order Traversal
原文：http://www.cnblogs.com/tritritri/p/4859874.html