题目：
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]] 题解： 这题同样是BFS，用一个flag记录是否需要reverse，如果需要的话就把reverse的结果存储即可。 代码如下：
1 public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { 2 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 3 4 if(root== null) 5 return res; 6 7 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); 8 queue.add(root); 9 10 int num = 0; 11 boolean reverse = false; // a flag 12 13 while(!queue.isEmpty()){ 14 num = queue.size(); 15 ArrayList<Integer> levelres = new ArrayList<Integer>(); 16 17 for( int i = 0; i<num; i++){ 18 TreeNode node = queue.poll(); 19 levelres.add(node.val); 20 21 if(node.left!= null) 22 queue.add(node.left); 23 if(node.right!= null) 24 queue.add(node.right); 25 } 26 27 if(reverse){ 28 Collections.reverse(levelres); 29 reverse = false; 30 } else{ 31 reverse = true; 32 } 33 res.add(levelres); 34 } 35 36 return res; 37 }
1 public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { 2 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 3 if(root == null) 4 return res; 5 6 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); 7 queue.add(root); 8 Boolean reverse = false; 9 int nextlevel = 0; 10 int currlevel = 1; 11 ArrayList<Integer> tmp = new ArrayList<Integer>(); 12 while(!queue.isEmpty()){ 13 TreeNode t = queue.poll(); 14 tmp.add(t.val); 15 currlevel--; 16 17 if(t.left!= null){ 18 queue.add(t.left); 19 nextlevel++; 20 } 21 22 if(t.right!= null){ 23 queue.add(t.right); 24 nextlevel++; 25 } 26 27 if(currlevel == 0){ 28 currlevel = nextlevel; 29 nextlevel = 0; 30 if(reverse){ 31 Collections.reverse(tmp); 32 reverse = false; 33 } else{ 34 reverse = true; 35 } 36 res.add(tmp); 37 tmp = new ArrayList<Integer>(); 38 } 39 } 40 41 return res; 42 }