剑指offer24 JZ78 把二叉树打印成多行

难点实现 每一层分层

思路

题目要求将二叉树按行打印，即按层打印，其中每层分开。不难想到，要使用层次遍历，但是难点在于如何每层分开存储，从哪里知晓分开的时机？在层次遍历的时候，我们通常会借助队列（queue），事实上，队列中的值大有玄机，让我们一起来看看：

• 当根节点进入队列时，队列长度为1，第一层节点数也为1
• 若是根节点有两个子节点，push进队列后，队列长度为2，第二层节点数也为2；若是根节点一个子节点， - push进队列后，队列长度为为1，第二层节点数也为1.
• 由此，我们可知，每层的节点数等于进入该层时队列长度，因为刚进入该层时，这一层每个节点都会push进队列，而上一层的节点都出去了。

每次只要在队列长度内循环，必定是一层，一层访问完毕再更新队列长度即可

import java.util.*;


/*
public 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<>();
        if(pRoot==null){
            return res;
        }
    
      Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(pRoot); //添加根节点
        while(!queue.isEmpty()){
            ArrayList<Integer> array=new ArrayList<>();
            //每层的节点个数等于  队列的长度
            int n=queue.size();
            //循环添加每一层
            for(int i=0;i<n;i++){
                TreeNode temp=queue.poll();
                 array.add(temp.val);
            if(temp.left!=null){
                queue.offer(temp.left);
            }
            if(temp.right!=null){
                queue.offer(temp.right);   
                }
            }
            res.add(array);   
    }
    return res;
}
}