剑指Offer:树的层次遍历，分层打印和按之字型打印

1.把二叉树打印成多行

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。 如：

1

2，3

3，4，5

解题：层次遍历使用队列，这里维护两个队列进行的区分cur，next，分别存储当前行节点和下一行节点，遍历完当前行cur后，两个队列再进行交换。

ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    	ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
    	if(pRoot==null)
    		return res;
    	Queue<TreeNode> cur=new LinkedList<>();
    	Queue<TreeNode> next=new LinkedList<>();
    	cur.offer(pRoot);
    	ArrayList<Integer> list=new ArrayList<>();
    	while(!cur.isEmpty()){
    		TreeNode pNode=cur.poll();
    		list.add(pNode.val);
    		if(pNode.left!=null)
    			next.offer(pNode.left);
    		if(pNode.right!=null)
    			next.offer(pNode.right);
    		if(cur.isEmpty()){
    			Queue<TreeNode> tmp=cur;
    			cur=next;
    			next=tmp;
    			res.add(list);
    			list=new ArrayList<>();
    		}
    	}
    	return res;
    }
           

如果不使用两个队列，就需要两个变量last,nlast，分别指向当前行的最后一个节点，和下一行的最后一个节点。如果访问的节点是当前行的最后一个节点last就表示当前行访问结束。

ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    	ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
    	if(pRoot==null)
    		return res;
    	Queue<TreeNode> q=new LinkedList<>();
    	q.offer(pRoot);
    	TreeNode last=pRoot,nlast=pRoot;
    	ArrayList<Integer> list=new ArrayList<>();
    	while(!q.isEmpty()){
    		TreeNode pNode=q.poll();
    		list.add(pNode.val);
    		if(pNode.left!=null){
    			q.offer(pNode.left);
    			nlast=pNode.left;
    		}	
    		if(pNode.right!=null){
    			q.offer(pNode.right);
    			nlast=pNode.right;
    		}	
    		if(pNode==last){
    			last=nlast;
    			res.add(list);
    			list=new ArrayList<>();
    		}    		
    	}
    	return res;
    }
           

2. 按之字形顺序打印二叉树

题目描述

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

1

3，2

4 ，5， 6， 7

这到题还是层次遍历，但遍历一层过后，遍历的顺序要相反，所以使用两个栈来当前层的节点和下一层的节点，但要注意根据访问的顺序是从左到右，还是从右到左，决定先访问左节点还是右节点。

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    	ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
    	Stack<TreeNode> cur=new Stack<>(); 
    	Stack<TreeNode> rev=new Stack<>();
    	cur.push(pRoot);
    	int flag=0;
    	ArrayList<Integer> list=new ArrayList<Integer>();
    	while(!cur.isEmpty()){   		
    		TreeNode pNode=cur.pop();
    		list.add(pNode.val);
    		if(flag==0){
    			if(pNode.left!=null)
    				rev.push(pNode.left);
    			if(pNode.right!=null)
    				rev.push(pNode.right);
    		}else if(flag!=0){
    			if(pNode.right!=null)
    				rev.push(pNode.right);
       			if(pNode.left!=null)
    				rev.push(pNode.left);
    		}
    		if(cur.isEmpty()){
    			Stack<TreeNode> tmp=cur;
    			cur=rev;
    			rev=tmp;
    			flag=1-flag;
    			res.add(list);
    			list=new ArrayList<Integer>();
    		}
    	}
    	return res;
    }