一，问题描述
请构造一棵二叉树，并按照“之字形”顺序打印这棵二叉树。
所谓“之字形”打印，第一行是从左到右打印，第二行是从右到左打印，第三行又是从左到右打印....
即，奇数行(根为第一行)是从左到右打印，而偶数行是从右到左打印。
如上图：该二叉树的打印顺序为：
20
30 10
12 25
二，问题分析
①定义两个栈一个名为 stack,另一个为nextStack，stack 只保存奇数行的结点，nextStack只保存偶数行的结点。并定义一个整形变量lineNumber 来标记行号，以判断当前打印的行是奇数行结点还是偶数行结点。
②当打印stack中的结点时，将该结点的孩子按照先 左孩子、后 右孩子的顺序 保存到nextStack栈中。
③当打印nextStack中的结点时，将该结点的孩子按照先 右孩子，后 左孩子的顺序 保存到 stack栈中。
复杂度分析：
由于每个结点都会入栈一次，然后出栈打印。故时间复杂度为O(N)
代码中使用了两个辅助栈，分别用来保存奇数行的结点和偶数行的结点。故空间复杂度也是O(N)
三，完整代码
import java.util.LinkedList; public class PrintZigzag { private class BinaryNode{ int ele; BinaryNode left; BinaryNode right; public BinaryNode(int ele) { this.ele = ele; left = right = null; } @Override public String toString() { return ele + " "; } } private BinaryNode root; //根据数组 arr 中的元素构造一棵二叉排序树 public void buildTree(int[] arr){ for (int node : arr) { insert(node); } } private void insert(int ele){ root = insert(root, ele); } private BinaryNode insert(BinaryNode root, int ele){ //递归的结束条件.base condition if(root == null) return new BinaryNode(ele); if(root.ele > ele) root.left = insert(root.left, ele); else if(root.ele < ele) root.right = insert(root.right, ele); else root.left = insert(root.left, ele); return root;//若某结点的左右孩子不空,在后续的递归调用中该结点的左右指针是不会变的. } public void zigPrintTree(){ if(root == null) return; LinkedList<BinaryNode> stack = new LinkedList<>();//打印当前行的栈(只保存奇数行的结点) LinkedList<BinaryNode> nextStack = new LinkedList<>();//打印下一行的栈(只保存偶数行的结点) int lineNumber = 1;//标记行号(根为第一行) stack.push(root);//根属于奇数行的结点(第一行) while(!stack.isEmpty() || !nextStack.isEmpty()) { if(lineNumber % 2 == 1)//奇数行,左孩子先入栈 { while(!stack.isEmpty()) { BinaryNode current = stack.pop(); System.out.print(current);//打印当前结点 if(current.left != null) nextStack.push(current.left);//先左孩子入栈 if(current.right != null) nextStack.push(current.right);//再右孩子入栈 } System.out.println();//该层结点已经打印完,输出换行符 }else{//偶数行,右孩子先入栈 while(!nextStack.isEmpty()) { BinaryNode current = nextStack.pop(); System.out.print(current); if(current.right != null)//先右孩子入栈 stack.push(current.right); if(current.left != null)//再左孩子入栈 stack.push(current.left); } System.out.println(); } lineNumber++; } } //hapjin test public static void main(String[] args) { int[] eles = {20,10,30,5,12,25,40}; // int[] eles = {20,10,30,12,25}; PrintZigzag pz = new PrintZigzag(); pz.buildTree(eles); pz.zigPrintTree(); } }
（注意：上面构造的是一棵二叉排序树）
四，参考资料