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

二叉树的层序遍历

层序遍历是广度优先搜索算法（Breadth First Search 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; } 

2. 使用队列先进先出的思想，但不使用辅助队列，而是用指针来实现。这种方式在时间复杂度上与第一种没什么区别，时间复杂度也为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