【题目】请实现一个函数按照之字形打印二叉树，
* 即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，
* 其他行以此类推。
未优化，不是最优解，博主用的是队列，我用的栈。
方法一：直接打印
package com.exe7.offer; import java.util.Stack; import org.junit.Test; /**方法一：直接打印
* 【题目】请实现一个函数按照之字形打印二叉树，
* 即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，
* 其他行以此类推。
* @author WGS
*
*/
public class PrintBiTree {
static class TreeNode{
int val=0;
TreeNode left=null;
TreeNode right=null;
public TreeNode(int val){
this.val=val;
}
} public void printZhiTree(TreeNode pRoot){
if(pRoot==null) return;
Stack<TreeNode> stack1=new Stack<>();
Stack<TreeNode> stack2=new Stack<>();
stack1.push(pRoot);
int toBePrint=1;
int nextLevelNodes=0;
int level=1;
TreeNode tempNode=null; while(!stack1.isEmpty() || !stack2.isEmpty()){
if(level%2!=0){
tempNode=stack1.pop();
System.out.print(tempNode.val+" ");
--toBePrint;
if(tempNode.left!=null){
stack2.push(tempNode.left);
++nextLevelNodes;
}
if(tempNode.right!=null){
stack2.push(tempNode.right);
++nextLevelNodes;
}
}else{
tempNode=stack2.pop();
System.out.print(tempNode.val+" ");
--toBePrint; if(tempNode.right!=null){
stack1.push(tempNode.right);
++nextLevelNodes;
}
if(tempNode.left!=null){
stack1.push(tempNode.left);
++nextLevelNodes;
}
}
//
if(toBePrint==0){
System.out.println("------------------");
level++;
toBePrint=nextLevelNodes;
nextLevelNodes=0;
}
} } //测试类
public static void main(String[] args){
PrintBiTree p=new PrintBiTree();
TreeNode root = new TreeNode(8);
TreeNode node1 = new TreeNode(6);
TreeNode node2 = new TreeNode(10);
TreeNode node3 = new TreeNode(5);
TreeNode node4 = new TreeNode(7);
TreeNode node5 = new TreeNode(9);
TreeNode node6 = new TreeNode(11);
TreeNode node7 = new TreeNode(12);
TreeNode node8 = new TreeNode(13);
TreeNode node9 = new TreeNode(14);
TreeNode node10 = new TreeNode(15);
TreeNode node11 = new TreeNode(16);
TreeNode node12 = new TreeNode(17);
TreeNode node13 = new TreeNode(18);
TreeNode node14 = new TreeNode(19); root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
node3.left=node7;
node3.right=node8;
node4.left=node9;
node4.right=node10;
node5.left=node11;
node5.right=node12;
node6.left=node13;
node6.right=node14; p.printZhiTree(root);
} }
方法二：面试需要
package com.exe7.offer; import java.util.ArrayList;
import java.util.Stack; /**方法二：面试时候需要
* 【题目】请实现一个函数按照之字形打印二叉树，
* 即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，
* 其他行以此类推。
* @author WGS
*
*/
public class PrintBiTree2 {
static class TreeNode{
int val=0;
TreeNode left=null;
TreeNode right=null;
public TreeNode(int val){
this.val=val;
}
} public ArrayList<ArrayList<Integer>> printZhiTree(TreeNode pRoot){
ArrayList<ArrayList<Integer>> list=new ArrayList<>();
if(pRoot==null) return list;
ArrayList<Integer> nodeList=new ArrayList<Integer>();
Stack<TreeNode> stack1=new Stack<>();
Stack<TreeNode> stack2=new Stack<>();
stack1.push(pRoot);
int toBePrint=1;
int nextLevelNodes=0;
int level=1;
TreeNode tempNode=null; while(!stack1.isEmpty() || !stack2.isEmpty()){
if(level%2!=0){//奇数层
tempNode=stack1.pop();
//System.out.print(tempNode.val+" ");
nodeList.add(tempNode.val);
--toBePrint;
if(tempNode.left!=null){
stack2.push(tempNode.left);
++nextLevelNodes;
}
if(tempNode.right!=null){
stack2.push(tempNode.right);
++nextLevelNodes;
} }else{
tempNode=stack2.pop();
//System.out.print(tempNode.val+" ");
nodeList.add(tempNode.val);
--toBePrint; if(tempNode.right!=null){
stack1.push(tempNode.right);
++nextLevelNodes;
}
if(tempNode.left!=null){
stack1.push(tempNode.left);
++nextLevelNodes;
}
/* if(toBePrint==0){
System.out.println();
list.add(nodeList);
level++;
toBePrint=nextLevelNodes;
nextLevelNodes=0;
nodeList=new ArrayList<Integer>();
}*/
}
if(toBePrint==0){
System.out.println();
list.add(nodeList);
level++;
toBePrint=nextLevelNodes;
nextLevelNodes=0;
nodeList=new ArrayList<Integer>();
}
}
return list; } //测试类
public static void main(String[] args){
PrintBiTree2 p=new PrintBiTree2();
TreeNode root = new TreeNode(8);
TreeNode node1 = new TreeNode(6);
TreeNode node2 = new TreeNode(10);
TreeNode node3 = new TreeNode(5);
TreeNode node4 = new TreeNode(7);
TreeNode node5 = new TreeNode(9);
TreeNode node6 = new TreeNode(11);
TreeNode node7 = new TreeNode(12);
TreeNode node8 = new TreeNode(13);
TreeNode node9 = new TreeNode(14);
TreeNode node10 = new TreeNode(15);
TreeNode node11 = new TreeNode(16);
TreeNode node12 = new TreeNode(17);
TreeNode node13 = new TreeNode(18);
TreeNode node14 = new TreeNode(19); root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
node3.left=node7;
node3.right=node8;
node4.left=node9;
node4.right=node10;
node5.left=node11;
node5.right=node12;
node6.left=node13;
node6.right=node14; ArrayList<ArrayList<Integer>> getList=p.printZhiTree(root);;
for(ArrayList<Integer> a:getList){
System.out.println(a);
} } }