1.题目描述
给定一颗二叉树,返回其节点值的层序遍历（即逐层地，从左到右访问所有节点）。
2,题目解析
既然要进行层序遍历,那么首先就得从根节点开始,依次遍历每一层的结果,那么如何保证我遍历的顺序呢?
我们可以和队列这种数据结构来配合使用,把上一层的结果,存放到队列里面去.然后在出上一层的元素的时候,同时把对应这个元素的left节点和right节点也加入到这个队列中去.这样就可以完成我们的层序遍历了.
接下来我将逐步实现这个过程.
1 把root节点加入进去
2 弹出这个节点的同时 加入它的子节点
3 弹出第二层的节点 然后在加入第三层的节点
接下来还有一个点,就是我们每次在弹出该层元素的时候,注意要记录一下有几个节点,这样我们就可以弹出这一层的所有元素并且加入下一层的元素了.
3.代码实现
每一行都有明确的注释,解释该行的作用.
public List<List<Integer>> levelOrder(TreeNode root) {//创建一个二维数组 来存放每一层的值List<List<Integer>> lists = new ArrayList<>();// 如果root == null 直接返回这个空二维数组即可if(root == null){return lists;}// 创建队列来存放节点Queue<TreeNode> queue = new LinkedList<>();//首先要在队列中加入rootqueue.add(root);//循环的跳出条件是queue为空 即队列中的所有元素都poll完了while (!queue.isEmpty()){//记录这一层需要多少次poll 和add操作int sz = queue.size();//临时数组 存放该层的值List<Integer> list = new ArrayList<>();for (int i = 0; i<sz;i++){//先弹出元素TreeNode node = queue.poll();//加入到临时数组中list.add(node.val);// 如果它的子节点为非空,在加入到队列,否则会抛异常if(node.left!=null){queue.add(node.left);}if(node.right!=null){queue.add(node.right);}}// 将这个临时队列加入到总队列中去lists.add(list);}//返回即可return lists;}
