package Exercises;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/*
 * 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，
 * 第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
 */
public class Test54 {
	public ArrayList<ArrayList<Integer>> print(TreeNode pRoot){
		//返回最后的结果
		ArrayList<ArrayList<Integer>> resultList=new ArrayList<>();
		//队列保存遍历2的顺序
		Queue<TreeNode> queue=new LinkedList<TreeNode>();
		//返回每一行的结果
		ArrayList<Integer> result=new ArrayList<>();
		boolean isLeftToRight=true;
		int begin=0;
		int end=1;
		//将根节点入队列
		queue.add(pRoot);
		while(!queue.isEmpty()){
			TreeNode currentNode=queue.poll();
			result.add(currentNode.val);
			begin++;
			if(currentNode.left!=null){
				queue.add(currentNode.left);
			}
			if(currentNode.right!=null){
				queue.add(currentNode.right);
			}
			//判断一行是否都添加到queue中
			if(begin==end){
				if(!isLeftToRight){
					resultList.add(revese(result));
				}else{
					resultList.add(result);
				}
				//下一行需要改变方向
				isLeftToRight=!isLeftToRight;
				end=queue.size();
				begin=0;
				result=new ArrayList<Integer>();
			}			
		}
		return resultList;	
	}

	private ArrayList<Integer> revese(ArrayList<Integer> result) {
		// TODO Auto-generated method stub
		   int size=result.size();
	       ArrayList<Integer> reverseResult=new ArrayList<Integer>();
	       for(int i = size - 1; i >= 0; i--){
	            reverseResult.add(result.get(i));
	        }
	        return reverseResult;
	}
	
	
	public static void main(String args[]){
		Test54 t=new Test54();
		 TreeNode ndoe4=new TreeNode(4);
		 TreeNode ndoe5=new TreeNode(5);
		 TreeNode ndoe6=new TreeNode(6);
		 TreeNode ndoe7=new TreeNode(7);
		 TreeNode node2=new TreeNode(2,ndoe4,ndoe5);
		 TreeNode node3=new TreeNode(3,ndoe6,ndoe7);
		 TreeNode root=new TreeNode(1,node2,node3);
		 ArrayList<ArrayList<Integer>> resultList=t.print(root);
		 for(ArrayList<Integer> result:resultList){
			 for(int i:result){
				 System.out.print(i+" ");
			 }
			 System.out.println();
		 }
	}
}