有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。
给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。

思路

按层次遍历二叉树,只要利用队列就可以实现了.但是要按层次打印的话必须要记录下每层的最后一个节点.这里我们采用两个变量last和nLast分别记录当前行的最后一个节点和目前已知的最后一个节点.当前遍历的节点为cur.

last初始值为root.由nLast负责更新.
nLast一直指向已经遍历的最后一个节点.队列中每加入一个节点,nLast就指向该节点. 并且当cur=last,更新last=nLast

上代码:

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class TreePrinter {
    public int[][] printTree(TreeNode root) {
        if(root==null) return null;
        ArrayList<ArrayList<Integer>> nodes=new ArrayList<>();
        ArrayList<Integer> curLine=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        TreeNode cur=null,last=root,nLast=null;
        while(!queue.isEmpty()){
            cur=queue.poll();
            curLine.add(cur.val);
            if(cur.left!=null){
                queue.offer(cur.left);
                nLast=cur.left;
            }
            if(cur.right!=null){
                queue.offer(cur.right);
                nLast=cur.right;
            }
            if(cur==last){        //节点等于last,说明到达了当前行的最后一个节点,
                nodes.add(curLine);
                last=nLast;
                curLine=new  ArrayList<Integer>();
            }
        }
        int[][]result=new int[nodes.size()][];
        for(int i=0;i<nodes.size();i++){
            curLine=nodes.get(i);
            result[i]=new int[curLine.size()];
            int j=0;
            for(Integer num:curLine){
               result[i][j++]=num;
            }
        } 
        return result;
    }
}