【题目】从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
方法一：直接打印
1 package com.exe7.offer; 2 3 import java.util.LinkedList; 4 import java.util.Queue; 5 6 /** 7 * 【题目】从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。 8 * @author WGS 9 * 10 */ 11 public class PrintBiTreeFromTopToBottom { 12 static class TreeNode{ 13 int val=0; 14 TreeNode left=null; 15 TreeNode right=null; 16 public TreeNode(int val){ 17 this.val=val; 18 } 19 } 20 21 public void printBiTreeFromTopToBottom(TreeNode headNode){ 22 if(headNode==null) return ; 23 int nextLevelNodes=0; 24 int toBoPrint=1;//设置个初始值 25 Queue<TreeNode> queue=new LinkedList<TreeNode>(); 26 queue.add(headNode); 27 while(!queue.isEmpty()){ 28 //1 打印 29 TreeNode curNode=queue.poll(); 30 System.out.print(curNode.val+" "); 31 32 //2 添加左右结点 33 if(curNode.left!=null){ 34 queue.add(curNode.left); 35 nextLevelNodes++;//下层要打印的结点数+1 36 } 37 if(curNode.right!=null){ 38 queue.add(curNode.right); 39 nextLevelNodes++;//下层要打印的结点数+1 40 } 41 //左右结点添加完后即打印完本层一个结点值，自动减1（要判断本层是否还有别的值） 42 --toBoPrint; 43 if(toBoPrint==0){//本层打印完 44 System.out.println();//换行 45 toBoPrint=nextLevelNodes;//下层要打印的结点数 46 nextLevelNodes=0;//清0 47 } 48 } 49 50 } 51 public static void main(String[] args) { 52 PrintBiTreeFromTopToBottom p=new PrintBiTreeFromTopToBottom(); 53 TreeNode root = new TreeNode(8); 54 TreeNode node1 = new TreeNode(6); 55 TreeNode node2 = new TreeNode(10); 56 TreeNode node3 = new TreeNode(5); 57 TreeNode node4 = new TreeNode(7); 58 TreeNode node5 = new TreeNode(9); 59 TreeNode node6 = new TreeNode(11); 60 61 root.left = node1; 62 root.right = node2; 63 node1.left = node3; 64 node1.right = node4; 65 node2.left = node5; 66 node2.right = node6; 67 68 p.printBiTreeFromTopToBottom(root); 69 } 70 71 }
方法二：使用博主的方法（面试时候推荐此种方法，个别代码差异，思想一样）
1 package com.exe7.offer; 2 3 import java.util.ArrayList; 4 import java.util.LinkedList; 5 import java.util.Queue; 6 7 /**方法二：使用博主的方法（面试时候推荐此种方法，个别代码差异，思想一样） 8 * 【题目】从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。 9 * @author WGS 10 * 11 */ 12 public class PrintBiTreeFromTopToBottom2 { 13 static class TreeNode{ 14 int val=0; 15 TreeNode left=null; 16 TreeNode right=null; 17 public TreeNode(int val){ 18 this.val=val; 19 } 20 } 21 22 public ArrayList<ArrayList<Integer>> printBiTreeFromTopToBottom(TreeNode headNode){ 23 ArrayList<ArrayList<Integer>> list=new ArrayList<>();//接收总共行的结点 24 ArrayList<Integer> nodeList=new ArrayList<>();//接收每行结点 25 if(headNode==null) return list; 26 int nextLevelNodes=0;//下层要打印的结点数 27 int toBoPrint=1;//设置个初始值 28 Queue<TreeNode> queue=new LinkedList<TreeNode>(); 29 queue.add(headNode); 30 while(!queue.isEmpty()){ 31 //1 打印 32 TreeNode curNode=queue.poll(); 33 //System.out.print(curNode.val+" "); 34 nodeList.add(curNode.val); 35 //2 添加左右结点 36 if(curNode.left!=null){ 37 queue.add(curNode.left); 38 nextLevelNodes++;//下层要打印的结点数+1 39 } 40 if(curNode.right!=null){ 41 queue.add(curNode.right); 42 nextLevelNodes++;//下层要打印的结点数+1 43 } 44 //左右结点添加完后即打印完本层一个结点值，自动减1（要判断本层是否还有别的值） 45 --toBoPrint; 46 if(toBoPrint==0){//本层打印完 47 //System.out.println();//换行 48 list.add(nodeList); 49 toBoPrint=nextLevelNodes;//下层要打印的结点数 50 nextLevelNodes=0;//清0 51 nodeList=new ArrayList<>(); 52 } 53 } 54 return list; 55 56 } 57 public static void main(String[] args) { 58 PrintBiTreeFromTopToBottom2 p=new PrintBiTreeFromTopToBottom2(); 59 TreeNode root = new TreeNode(8); 60 TreeNode node1 = new TreeNode(6); 61 TreeNode node2 = new TreeNode(10); 62 TreeNode node3 = new TreeNode(5); 63 TreeNode node4 = new TreeNode(7); 64 TreeNode node5 = new TreeNode(9); 65 TreeNode node6 = new TreeNode(11); 66 67 root.left = node1; 68 root.right = node2; 69 node1.left = node3; 70 node1.right = node4; 71 node2.left = node5; 72 node2.right = node6; 73 74 ArrayList<ArrayList<Integer>> getList=p.printBiTreeFromTopToBottom(root); 75 for (ArrayList<Integer> arrayList : getList) { 76 System.out.println(arrayList); 77 } 78 } 79 80 }