有一棵二叉樹，請設(shè)計一個算法，按照層次打印這棵二叉樹。
給定二叉樹的根結(jié)點root，請返回打印結(jié)果，結(jié)果按照每一層一個數(shù)組進行儲存，所有數(shù)組的順序按照層數(shù)從上往下，且每一層的數(shù)組內(nèi)元素按照從左往右排列。保證結(jié)點數(shù)小于等于500。

思路

按層次遍歷二叉樹,只要利用隊列就可以實現(xiàn)了.但是要按層次打印的話必須要記錄下每層的最后一個節(jié)點.這里我們采用兩個變量last和nLast分別記錄當(dāng)前行的最后一個節(jié)點和目前已知的最后一個節(jié)點.當(dāng)前遍歷的節(jié)點為cur.

last初始值為root.由nLast負(fù)責(zé)更新.
nLast一直指向已經(jīng)遍歷的最后一個節(jié)點.隊列中每加入一個節(jié)點,nLast就指向該節(jié)點. 并且當(dāng)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){        //節(jié)點等于last,說明到達了當(dāng)前行的最后一個節(jié)點,
                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;
    }
}