这道题会考察很多知识点,这里专门进行详解

题目描述

二. 题目分析

首先,我们会想到存储方式为二维数组.数组每一行存储一层的结点.怎么确定每一行要存储几个结点呢.由于节点与节点之间存在父子关系,所以,在存储某一层的结点时,就可以通过存储这一层节点的左右孩子,来记录下一层的结点.
首先,定义二维数组,数组每一行存储一层的结点.

ArrayList<ArrayList<Integer>> list = new ArrayList<>();

先把一层的结点先放到队列中,记录好一层节点的数目size

再依次取出来,放到ArrayList里,用size控制好这一层的数目.由于队列先进先出,不会打乱节点顺序.
在取出结点的同时,将结点的左右孩子结点放入队列,一层的节点全部放进去之后,会再次记录size值.如下图

之后,重复操作,取出这一层的节点值,同时,把他们的左右孩子放进队列,进行计数.

直到队列为空,结束循环.

完整代码

	public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {// 层序遍历ArrayList<ArrayList<Integer>> list = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if(root == null){return list;}//把根节点放进去queue.offer(root);while(!queue.isEmpty()){int size = queue.size();//注意arr的位置,一定要放在外循环里ArrayList<Integer> arr = new ArrayList<>();while(size > 0){TreeNode cur = queue.poll();size--;if(cur != null){arr.add(cur.val);}if(cur.left != null){queue.offer(cur.left);}if(cur.right != null){queue.offer(cur.right);}}list.add(arr);}return list;}