JZ78 把二叉树打印成多行

题目

给定一个节点数为 n 二叉树    
    
    
，要求从上到下按层打印二叉树的 val 值   


     


     


 ，同一层结点从左至右输出



 




 




 ，每一层输出一行   

   

   

， 将输出的结果存放到一个二维数组中返回    
    
    
。 例如：给定的二叉树是{1,2,3,#,#,4,5} [ [1], [2,3], [4,5] ]

方法 非递归层次遍历

思路

算法实现

按照层次遍历按层打印二叉树的方式    

     

     

，每层分开打印




  




  




  ，记录数组   


     


     


 。 具体做法： step 1：如果树为空  


  


  

，则返回空数组     
     
     
，没有任何打印结果



 




 




 。 step 2：使用队列辅助层次遍历




   




   




  ，优先加入二叉树的根节点   

   

   

。 step 3：从根节点开始
 



 



 

，每次进入一层的时候               ，记录队列的长度即本层的节点数 




    




    




  ， 然后访问相应节点数全在同一个数组中













，子节点加入队列中继续排队    

     

     

。 step 4：每次访问完一层将数组加入二维数组中再进入下一层




  




  




  。

代码

package mid.JZ78把二叉树打印成多行; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } public class Solution { ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) { //存放结果 ArrayList<ArrayList<Integer>> res = new ArrayList<>(); //如果根节点为null 直接返回 if (pRoot == null) return res; //定义队列进行广度遍历 Queue<TreeNode> queue = new LinkedList<>(); queue.offer(pRoot); while (!queue.isEmpty()) { //记录每一层有几个节点 int size = queue.size(); //记录每一层的数据 ArrayList<Integer> row = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null) { //左子树有值               ，入队 queue.offer(node.left); } if (node.right != null) { //右子树有值  



     



     



  ，入队 queue.offer(node.right); } //将值添加到层集合中 row.add(node.val); } res.add(row); } return res; } }