1.题目:
从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
输入 {8,6,10,5,7,9,11} 返回值 [[8],[6,10],[5,7,9,11]]
2.思路;
其实就是层序遍历:此题最重要的是使用队列,并且记录队列的长度!!!时间复杂度:O(n)
题目给的是ArrayList<ArrayList<integer>>:其实是让你返回一个ArrayList,其中每个元素都是一个装了整型数据的ArrayList。比如{[8],[9,10],[11,12,13]}这样的返回方式。比如树有3层,大括号表示的ArrayList就应该装了3个元素。中括号的ArrayList就表示这颗树某一层的所有节点。用这样的方式来区别换行。
返回类型是ArrayList<ArrayList<integer> >时,不能只new一个,之前分析的有[8],[9,10],[11,12,13]这样的3个ArrayList,因此每while一次(每遍历一层),都需要重新new一个ArrayList存放当前层的所有节点。</integer></integer>
import java.util.Queue; import java.util.LinkedList; public class Solution { ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> res=new ArrayList<>();//返回答案嵌套[1][234][56789].... ArrayList<Integer> list=new ArrayList<>();//存储每一层的值[234] Queue<TreeNode> queue=new LinkedList<>();//存储每一层的节点 if(pRoot==null){ return res; } TreeNode cur;//当前出队列的节点 queue.offer(pRoot);//增加节点offer比add好点/在满了的时候返回为null而不是抛出异常 int count=0;//记录当前队列的长度 while(!queue.isEmpty()){ count=queue.size(); list=new ArrayList<>();//每一层都用一个新的集合来存储 while(count>0){//将每一层都循环输出,并且每个的子节点入队列 cur=queue.poll(); list.add(cur.val); if(cur.left!=null) queue.offer(cur.left); if(cur.right!=null) queue.offer(cur.right); count--; } res.add(list); } return res; } }