之字形顺序打印二叉树

编程练习

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

思路：利用之前写好的层序遍历打印代码，将层数控制加入即可，注意偶数层翻转即可。

java代码如下：

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

public class ZigZagPrint {
	/**
	 * 统计层数，最后判断是不是偶数层，偶数层调用reverse方法
	 * @param pRoot
	 * @return
	 */
	 public static ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
		 
		 ArrayList<ArrayList<Integer>> reslist=new ArrayList<ArrayList<Integer>>();
		 Queue<TreeNode> treeQueue=new LinkedList<TreeNode>();
		 if (pRoot==null) {
			 return reslist;
		 }
		 treeQueue.add(pRoot);
		 int level=0;
		 while(!treeQueue.isEmpty()) {
			 level++;
			 ArrayList<Integer> valList=new ArrayList<Integer>();
			 int len=treeQueue.size();
			 
			 for(int i=0;i<len;i++) {
				 TreeNode node=treeQueue.poll();
				 valList.add(node.val);
		    	 if(node.left!=null) {
		    		 treeQueue.add(node.left);
		    	 }
		    	 if(node.right!=null) {
		    		 treeQueue.add(node.right);
		    	 }
			 }
			 
			 if(level%2==0) {
				 Collections.reverse(valList);
			 }
			 
			 reslist.add(valList);
		 }
		 return reslist;
	 }
	 public static void main(String[] args) {
		 TreeNode root=new TreeNode(0);
			TreeNode node1=new TreeNode(1);
			TreeNode node2=new TreeNode(2);
			TreeNode node3=new TreeNode(3);
			TreeNode node4=new TreeNode(4);
			TreeNode node5=new TreeNode(5);
			
			root.left=node1;
			root.right=node2;
			node1.left=node3;
			node1.right=node4;
			node2.left=node5;
			System.out.println(Print(root));
	}
}