/*
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，
第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
*/

import java.util.*;

public class Class63 {

public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;
}
}

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot){
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list = new ArrayList<Integer>();
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
if(pRoot == null){
return result;
}
queue.addLast(null);
queue.addLast(pRoot);
boolean leftToRight = true;
while(queue.size() != 1){
TreeNode node = queue.removeFirst();
if(node == null){
//使用一个迭代器
Iterator<TreeNode> iter = null;
if(leftToRight){
iter = queue.iterator();
}else{
iter = queue.descendingIterator();
}
leftToRight = !leftToRight;
while(iter.hasNext()){
TreeNode temp = (TreeNode)iter.next();
list.add(temp.val);
}
result.add(new ArrayList<Integer>(list)); //为了防止指向同一个list
list.clear();
queue.addLast(null);
continue;
}
if(node.left != null){
queue.addLast(node.left);
}
if(node.right != null){
queue.addLast(node.right);
}
}
return result;
}

public static void main(String[] args) {
// TODO Auto-generated method stub

}

}