赞
踩
对于二叉树的层序遍历,我们可以使用广度优先搜索解决。
思路分析:
1:定义一个队列,利用队列先进先出的准则,先将根节点存入到队列中
2:当队列中元素不为空时,记录队列中的元素个数,并依次取出队列中的节点元素,并将取出的元素添加到子集合中去。当节点元素有左子树或者右子树时,将左子树或者右子树入队列
3:再次统计队列中的新加入节点后的所有节点个数并且依次取出,重复上述操作,就能逐层的遍历二叉树
- class Solution {
- public List<List<Integer>> levelOrder(TreeNode root) {
- List<List<Integer>> list=new ArrayList<>();
- //先对根节点是否为空值进行判断
- if(root==null){
- return list;
- }
- //定义一个队列用于存放二叉树的每一层的节点
- Queue<TreeNode> queue=new LinkedList<>();
- //先把二叉树根节点存放到队列中
- queue.offer(root);
- //当队列中没有节点时推出循环
- while(!queue.isEmpty()){
- //定义子集合,用于存放二叉树每一层的节点的值
- List<Integer> subList=new ArrayList<>();
- //定义一个记录队列中元素个数的变量
- int size=queue.size();
- for(int i=0;i<size;i++){
- //定义一个节点,记录队列中的元素,并依次将队列中的元素出队列
- TreeNode node=queue.poll();
- //将出队列中的元素依次添加到子集合中
- subList.add(node.val);
- //判断当前根节点的左右节点是否存在
- //如果当前根节点有左子树,则将左子节点添加到队列中
- if(node.left!=null){
- queue.offer(node.left);
- }
- //如果当前根节点有右子树,则将右子节点添加到队列中
- if(node.right!=null){
- queue.offer(node.right);
- }
- }//第i轮循环后,即二叉树的第i层的所有节点信息全部进入队列中
- //将队列中的信息存放到集合中
- list.add(subList);
- }
- return list;
- }
- }
在遍历完一层节点之后,将存储该层节点值的列表添加到结果列表的头部。 就能实现自底向上的层序遍历
- class Solution {
- public List<List<Integer>> levelOrderBottom(TreeNode root) {
- //初始化一个集合
- List<List<Integer>> list=new ArrayList<>();
- //判断根节点是否为空
- if(root==null){
- return list;
- }
- //初始化栈,利用栈先进后出的准则,实现自底向上的层序遍历
- Queue<TreeNode> queue=new LinkedList<>();
- //将根节点压入栈底
- queue.offer(root);
- while(!queue.isEmpty()){
- //初始化一个子集合
- List<Integer> subList=new ArrayList<>();
- //定义一个变量用于统计栈中的元素个数
- int size=queue.size();
- for(int i=0;i<size;i++){
- //定义一个node变量,用于接收出栈的节点信息
- TreeNode node = queue.poll();
- //每遍历一次栈中的元素,就把弹出栈的元素加入到集合中
- subList.add(node.val);
- //判断根节点是否有左右子树
- //判断根节点的左子树是否为空
- if(node.left!=null){
- //将左子节点压入栈
- queue.offer(node.left);
- }
- //判断根节点的右子树是否为空
- if(node.right!=null){
- //将右子节点压入栈
- queue.offer(node.right);
- }
- }
- //在遍历完一层节点之后,将存储该层节点值的列表添加到结果列表的头部。
- list.add(0,subList);
- }
- return list;
- }
-
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。