欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

两种方式实现二叉树BFS层序遍历

程序员文章站 2022-06-28 17:17:27
二叉树的层序遍历层序遍历是广度优先搜索算法(Breadth First Search BFS)的体现,而BFS通常利用队列的先进先出特性来实现。(当然递归方式也能实现)给定某二叉树如下图所示(图片来源于网络):利用辅助队列,时间复杂度为O(n),n为节点数。BFS初始化:将根节点加入队列(此时队列中就只有根节点一个元素)BFS循环:当队列为空时跳出循环1.队首元素出队(队首元素发生改变),并记录该节点值2.将出队的队首节点的左右子节点依次添加到队列中(若无则跳过)public int[...

二叉树的层序遍历

层序遍历是广度优先搜索算法(Breadth First Search BFS)的体现,而BFS通常利用队列的先进先出特性来实现。(当然递归方式也能实现)

给定某二叉树如下图所示(图片来源于网络):
两种方式实现二叉树BFS层序遍历

  1. 利用辅助队列,时间复杂度为O(n),n为节点数。
    BFS初始化:将根节点加入队列(此时队列中就只有根节点一个元素)
    BFS循环:当队列为空时跳出循环
    1.队首元素出队(队首元素发生改变),并记录该节点值
    2.将出队的队首节点的左右子节点依次添加到队列中(若无则跳过)
public int[] levelOrder(TreeNode root) { if(root == null) return new int[0]; //初始化 Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }}; ArrayList<Integer> ans = new ArrayList<>(); //BFS循环 while(!queue.isEmpty()) { TreeNode node = queue.poll(); ans.add(node.val); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } int[] res = new int[ans.size()]; for(int i = 0; i < ans.size(); i++) res[i] = ans.get(i); return res; } 
  1. 使用队列先进先出的思想,但不使用辅助队列,而是用指针来实现。这种方式在时间复杂度上与第一种没什么区别,时间复杂度也为O(n),n为节点数。,不过在空间复杂度上会节省一些。
    初始化:将根节点加入到集合中,并初始化指针i。
    BFS循环:当指针越过集合的最后一个元素时跳出
    1. 将指针所指的“队首”元素的左右子节点依次加入队列(若有)
    2.指针i往后移一位,然后循环
class Solution { public int[] levelOrder(TreeNode root) { if (root==null) return new int[0]; //初始化  List<TreeNode> list=new ArrayList<>(); int i=0; list.add(root); //BFS循环 while (i<list.size()){ TreeNode mid=list.get(i); if (mid.left!=null) list.add(mid.left); if (mid.right!=null) list.add(mid.right); i++; } int [] res=new int[list.size()]; for (int j=0;j<list.size();j++) res[j]=list.get(j).val; return res; } } 

本文地址:https://blog.csdn.net/qq_39435967/article/details/108033279