package com.exe7.offer;

 import java.util.LinkedList;

 import java.util.Queue;

 /**

  * 【题目】从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

  * @author WGS

  *

  */

 public class PrintBiTreeFromTopToBottom {

     static class TreeNode{

         int val=0;

         TreeNode left=null;

         TreeNode right=null;

         public TreeNode(int val){

             this.val=val;

         }

     }

     public void printBiTreeFromTopToBottom(TreeNode headNode){

         if(headNode==null) return ;

         int nextLevelNodes=0;

         int toBoPrint=1;//设置个初始值

         Queue<TreeNode> queue=new LinkedList<TreeNode>();

         queue.add(headNode);

         while(!queue.isEmpty()){

             //1 打印

             TreeNode curNode=queue.poll();

             System.out.print(curNode.val+"  ");

             //2 添加左右结点

             if(curNode.left!=null){

                 queue.add(curNode.left);

                 nextLevelNodes++;//下层要打印的结点数+1

             }

             if(curNode.right!=null){

                 queue.add(curNode.right);

                 nextLevelNodes++;//下层要打印的结点数+1

             }

             //左右结点添加完后即打印完本层一个结点值，自动减1（要判断本层是否还有别的值）

             --toBoPrint;

             if(toBoPrint==0){//本层打印完

                 System.out.println();//换行

                 toBoPrint=nextLevelNodes;//下层要打印的结点数

                 nextLevelNodes=0;//清0

             }

         }

     }

     public static void main(String[] args) {

         PrintBiTreeFromTopToBottom p=new PrintBiTreeFromTopToBottom();

          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);

             root.left = node1;

             root.right = node2;

             node1.left = node3;

             node1.right = node4;

             node2.left = node5;

             node2.right = node6;

            p.printBiTreeFromTopToBottom(root);

     }

 }

 package com.exe7.offer;

 import java.util.ArrayList;

 import java.util.LinkedList;

 import java.util.Queue;

 /**方法二：使用博主的方法（面试时候推荐此种方法，个别代码差异，思想一样）

  * 【题目】从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

  * @author WGS

  *

  */

 public class PrintBiTreeFromTopToBottom2 {

     static class TreeNode{

         int val=0;

         TreeNode left=null;

         TreeNode right=null;

         public TreeNode(int val){

             this.val=val;

         }

     }

     public ArrayList<ArrayList<Integer>> printBiTreeFromTopToBottom(TreeNode headNode){

         ArrayList<ArrayList<Integer>> list=new ArrayList<>();//接收总共行的结点

         ArrayList<Integer> nodeList=new ArrayList<>();//接收每行结点

         if(headNode==null) return list;

         int nextLevelNodes=0;//下层要打印的结点数

         int toBoPrint=1;//设置个初始值

         Queue<TreeNode> queue=new LinkedList<TreeNode>();

         queue.add(headNode);

         while(!queue.isEmpty()){

             //1 打印

             TreeNode curNode=queue.poll();

             //System.out.print(curNode.val+"  ");

             nodeList.add(curNode.val);

             //2 添加左右结点

             if(curNode.left!=null){

                 queue.add(curNode.left);

                 nextLevelNodes++;//下层要打印的结点数+1

             }

             if(curNode.right!=null){

                 queue.add(curNode.right);

                 nextLevelNodes++;//下层要打印的结点数+1

             }

             //左右结点添加完后即打印完本层一个结点值，自动减1（要判断本层是否还有别的值）

             --toBoPrint;

             if(toBoPrint==0){//本层打印完

                 //System.out.println();//换行

                 list.add(nodeList);

                 toBoPrint=nextLevelNodes;//下层要打印的结点数

                 nextLevelNodes=0;//清0

                 nodeList=new ArrayList<>();

             }

         }

         return list;

     }

     public static void main(String[] args) {

         PrintBiTreeFromTopToBottom2 p=new PrintBiTreeFromTopToBottom2();

          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);

             root.left = node1;

             root.right = node2;

             node1.left = node3;

             node1.right = node4;

             node2.left = node5;

             node2.right = node6;

             ArrayList<ArrayList<Integer>> getList=p.printBiTreeFromTopToBottom(root);

             for (ArrayList<Integer> arrayList : getList) {

                 System.out.println(arrayList);

             }

     }

 }