有一棵二叉树,请设计一个算法,按照层次打印这棵二叉树。
给定二叉树的根结点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;
}
}