剑指offer系列34----按之字形顺序打印二叉树

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

未优化，不是最优解，博主用的是队列，我用的栈。

方法一：直接打印

  1 package com.exe7.offer;
  2 
  3 import java.util.Stack;
  4 
  5 import org.junit.Test;
  6 
  7 
  8 
  9 /**方法一：直接打印
 10  * 【题目】请实现一个函数按照之字形打印二叉树，
 11  *             即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，
 12  *        其他行以此类推。
 13  * @author WGS
 14  *
 15  */
 16 public class PrintBiTree {
 17     static class TreeNode{
 18         int val=0;
 19         TreeNode left=null;
 20         TreeNode right=null;
 21         public TreeNode(int val){
 22             this.val=val;
 23         }
 24     }
 25     
 26     
 27     public void printZhiTree(TreeNode pRoot){
 28         if(pRoot==null) return;
 29         Stack<TreeNode> stack1=new Stack<>();
 30         Stack<TreeNode> stack2=new Stack<>();
 31         stack1.push(pRoot);
 32         int toBePrint=1;
 33         int nextLevelNodes=0;
 34         int level=1;
 35         TreeNode tempNode=null;
 36         
 37         while(!stack1.isEmpty() || !stack2.isEmpty()){
 38             if(level%2!=0){
 39                 tempNode=stack1.pop();
 40                 System.out.print(tempNode.val+" ");
 41                 --toBePrint;
 42                 if(tempNode.left!=null){
 43                     stack2.push(tempNode.left);
 44                     ++nextLevelNodes;
 45                 }
 46                 if(tempNode.right!=null){
 47                     stack2.push(tempNode.right);
 48                     ++nextLevelNodes;
 49                 }
 50             }else{
 51                 tempNode=stack2.pop();
 52                 System.out.print(tempNode.val+" ");
 53                 --toBePrint;
 54                 
 55                 if(tempNode.right!=null){
 56                     stack1.push(tempNode.right);
 57                     ++nextLevelNodes;
 58                 }
 59                 if(tempNode.left!=null){
 60                     stack1.push(tempNode.left);
 61                     ++nextLevelNodes;
 62                 }
 63             }
 64             //
 65             if(toBePrint==0){
 66                 System.out.println("------------------");
 67                 level++;
 68                 toBePrint=nextLevelNodes;
 69                 nextLevelNodes=0;
 70             }
 71         }
 72         
 73         
 74     }
 75     
 76     //测试类
 77         public static void main(String[] args){
 78             PrintBiTree p=new PrintBiTree();
 79              TreeNode root = new TreeNode(8);
 80                 TreeNode node1 = new TreeNode(6);
 81                 TreeNode node2 = new TreeNode(10);
 82                 TreeNode node3 = new TreeNode(5);
 83                 TreeNode node4 = new TreeNode(7);
 84                 TreeNode node5 = new TreeNode(9);
 85                 TreeNode node6 = new TreeNode(11);
 86                 TreeNode node7 = new TreeNode(12);
 87                 TreeNode node8 = new TreeNode(13);
 88                 TreeNode node9 = new TreeNode(14);
 89                 TreeNode node10 = new TreeNode(15);
 90                 TreeNode node11 = new TreeNode(16);
 91                 TreeNode node12 = new TreeNode(17);
 92                 TreeNode node13 = new TreeNode(18);
 93                 TreeNode node14 = new TreeNode(19);
 94 
 95                 root.left = node1;
 96                 root.right = node2;
 97                 node1.left = node3;
 98                 node1.right = node4;
 99                 node2.left = node5;
100                 node2.right = node6;
101                 node3.left=node7;
102                 node3.right=node8;
103                 node4.left=node9;
104                 node4.right=node10;
105                 node5.left=node11;
106                 node5.right=node12;
107                 node6.left=node13;
108                 node6.right=node14;
109                 
110                 
111                 p.printZhiTree(root);
112         }
113 
114     
115     
116     
117     
118 }

方法二：面试需要

  1 package com.exe7.offer;
  2 
  3 import java.util.ArrayList;
  4 import java.util.Stack;
  5 
  6 
  7 
  8 
  9 /**方法二：面试时候需要
 10  * 【题目】请实现一个函数按照之字形打印二叉树，
 11  *             即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，
 12  *        其他行以此类推。
 13  * @author WGS
 14  *
 15  */
 16 public class PrintBiTree2 {
 17     static class TreeNode{
 18         int val=0;
 19         TreeNode left=null;
 20         TreeNode right=null;
 21         public TreeNode(int val){
 22             this.val=val;
 23         }
 24     }
 25     
 26     
 27     public ArrayList<ArrayList<Integer>>  printZhiTree(TreeNode pRoot){
 28         ArrayList<ArrayList<Integer>> list=new ArrayList<>();
 29         if(pRoot==null) return list;
 30         ArrayList<Integer> nodeList=new ArrayList<Integer>();
 31         Stack<TreeNode> stack1=new Stack<>();
 32         Stack<TreeNode> stack2=new Stack<>();
 33         stack1.push(pRoot);
 34         int toBePrint=1;
 35         int nextLevelNodes=0;
 36         int level=1;
 37         TreeNode tempNode=null;
 38         
 39         while(!stack1.isEmpty() || !stack2.isEmpty()){
 40             if(level%2!=0){//奇数层
 41                 tempNode=stack1.pop();
 42                 //System.out.print(tempNode.val+" ");
 43                 nodeList.add(tempNode.val);
 44                 --toBePrint;
 45                 if(tempNode.left!=null){
 46                     stack2.push(tempNode.left);
 47                     ++nextLevelNodes;
 48                 }
 49                 if(tempNode.right!=null){
 50                     stack2.push(tempNode.right);
 51                     ++nextLevelNodes;
 52                 }
 53                 
 54             }else{
 55                 tempNode=stack2.pop();
 56                 //System.out.print(tempNode.val+" ");
 57                 nodeList.add(tempNode.val);
 58                 --toBePrint;
 59                 
 60                 if(tempNode.right!=null){
 61                     stack1.push(tempNode.right);
 62                     ++nextLevelNodes;
 63                 }
 64                 if(tempNode.left!=null){
 65                     stack1.push(tempNode.left);
 66                     ++nextLevelNodes;
 67                 }
 68             /*    if(toBePrint==0){
 69                     System.out.println();
 70                     list.add(nodeList);
 71                     level++;
 72                     toBePrint=nextLevelNodes;
 73                     nextLevelNodes=0;
 74                     nodeList=new ArrayList<Integer>();
 75                 }*/
 76             }
 77             if(toBePrint==0){
 78                 System.out.println();
 79                 list.add(nodeList);
 80                 level++;
 81                 toBePrint=nextLevelNodes;
 82                 nextLevelNodes=0;
 83                 nodeList=new ArrayList<Integer>();
 84             }
 85         }
 86         return list;
 87         
 88         
 89     }
 90     
 91     //测试类
 92         public static void main(String[] args){
 93             PrintBiTree2 p=new PrintBiTree2();
 94              TreeNode root = new TreeNode(8);
 95                 TreeNode node1 = new TreeNode(6);
 96                 TreeNode node2 = new TreeNode(10);
 97                 TreeNode node3 = new TreeNode(5);
 98                 TreeNode node4 = new TreeNode(7);
 99                 TreeNode node5 = new TreeNode(9);
100                 TreeNode node6 = new TreeNode(11);
101                 TreeNode node7 = new TreeNode(12);
102                 TreeNode node8 = new TreeNode(13);
103                 TreeNode node9 = new TreeNode(14);
104                 TreeNode node10 = new TreeNode(15);
105                 TreeNode node11 = new TreeNode(16);
106                 TreeNode node12 = new TreeNode(17);
107                 TreeNode node13 = new TreeNode(18);
108                 TreeNode node14 = new TreeNode(19);
109 
110                 root.left = node1;
111                 root.right = node2;
112                 node1.left = node3;
113                 node1.right = node4;
114                 node2.left = node5;
115                 node2.right = node6;
116                 node3.left=node7;
117                 node3.right=node8;
118                 node4.left=node9;
119                 node4.right=node10;
120                 node5.left=node11;
121                 node5.right=node12;
122                 node6.left=node13;
123                 node6.right=node14;
124                 
125                 ArrayList<ArrayList<Integer>> getList=p.printZhiTree(root);;
126                 for(ArrayList<Integer> a:getList){
127                     System.out.println(a);
128                 }
129                 
130         }
131 
132     
133     
134     
135     
136 }