劍指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;
    }