【LeetCode Cookbook(C++ 描述)】一刷二叉树之层序遍历(BFS)

目录

  • LeetCode #102:Binary Tree Lever Order Traversal 二叉树的层序遍历
    • 递归解法
    • 迭代解法
  • LeetCode #107:Binary Tree Level Order Traversal II - 二叉树的层序遍历 II
    • 递归解法
    • 迭代解法
  • LeetCode #429:N-ary Tree Level Order Traversal - N 叉树的层序遍历
  • LeetCode #637:Average of Levels in Binary Tree 二叉树的层平均值
    • 广度优先搜索(BFS)
    • 深度优先搜索(DFS)

本系列文章仅是 GitHub 大神 @halfrost 的刷题笔记 《LeetCode Cookbook》的提纲以及示例、题集的 C++转化。原书请自行下载学习。
本篇文章涉及新手应该优先刷的几道经典二叉树层序遍历算法题。

LeetCode #102:Binary Tree Lever Order Traversal 二叉树的层序遍历

#102
给你一个二叉树,请你返回其按层序遍历得到的节点值。

递归解法

递归法并不符合层序遍历的初衷。递归是基于深度的,通过“解决到底”(即达到基准情况)将问题分解成规模更小的相同问题,直到问题小到可以直接解决(这被称为基准情况或递归终止条件),然后将这些小规模问题的解合并起来,即逐步回溯,形成原问题的解,而层序遍历需要一层一层地遍历,这显然不太符合广度优先搜索(BFS)的基本思想。

但是,我们依然可以利用递归实现二叉树的层序遍历。层序遍历是每一层的节点从左到右的遍历,在遍历的时候我们可以先遍历左子树,再遍历右子树。假设我们有如图的一颗二叉树:

在这里插入图片描述

遍历的顺序应为:3 -> 9 -> 3 -> 20 -> 15 -> 20 -> 7

因此,在遍历左子树或者右子树的时候,涉及到向上或者向下遍历,为了让递归的过程中的同
一层的节点放在同一个列表中,在递归时要记录深度 depth ;同时,每次遍历到一个新的 depth ,结果数组中没有对应 depth 的列表时,则在结果数组中创建一个新的列表保存该 depth 的节点。

//若当前行对应的列表不存在,则添加一个空列表
if (res.size() < depth) res.push_back(vector<int>());

我们利用递归的性质,每次向下深入均记录一次深度,并将相应节点值存储在对应深度的数组中,最终返回一个二维数组。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (root == nullptr) return res;level(root, 1, res);return res;}private:void level(TreeNode* root, int depth, vector<vector<int>>& res) {if (root == nullptr) return;  // base case//若当前行对应的列表不存在,则添加一个空列表if (res.size() < depth) res.push_back(vector<int>());//将当前节点的值添加到当前深度的列表中res[depth - 1].push_back(root->val);//递归处理左子树if (root->left) level(root->left, depth + 1, res);//递归处理右子树if (root->right) level(root->right, depth + 1, res);}
};

该算法的时间复杂度为 O ( n ) \ O(n)  O(n) ,由于维护了一个结果数组 res ,空间复杂度为 O ( n ) \ O(n)  O(n)

需要注意的是,尽管这一解法使用了递归,但它在这里更多地是作为一种遍历树的手段,通过深度来控制每一层数据的收集。这种方法的优点是代码简洁,但不是处理大型二叉树时最高效的方法,过深的递归深度可能会导致栈溢出。对于大型树,迭代法更合适

迭代解法

我们利用队列保存每一层的所有节点,把队列里的所有节点弹出队列,然后把这些节点各自的子节点入队列,以此来完成对每一层的遍历。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (root == nullptr) return res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int levelSize = q.size();   //当前层的节点数vector<int> currentLevel;for (int i = 0; i < levelSize; ++i) {TreeNode* node = q.front();q.pop();//将当前节点的值加入当前层的结果中currentLevel.push_back(node->val); //若节点存在左子树,入队if (node->left) q.push(node->left);//若节点存在右子树,入队if (node->right) q.push(node->right);}//将当前层的结果加入最终结果中res.push_back(currentLevel); }return res;}
};

LeetCode #107:Binary Tree Level Order Traversal II - 二叉树的层序遍历 II

#107
给你二叉树的根节点 root ,返回其节点值自底向上的层序遍历(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)。

与 #102 题(上一题)原理一致,按照正常层序遍历,获得结果后再将其逆序输出即可。

递归解法

我们依然是先遍历左子树,再遍历右子树,在递归时记录深度 depth ,不断更新每一层的 depth ,采用的 level() 方法与 #102 题一致。

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> res;level(root, 1, res);reverse(res.begin(), res.end());   //反转结果return res;}private:void level(TreeNode* root, int depth, vector<vector<int>>& res) {if (root == nullptr) return;//若当前行对应的列表不存在,加一个空列表if (res.size() < depth) res.push_back(std::vector<int>());//将当前节点的值加入当前行的res中res[depth - 1].push_back(root->val);//递归处理左子树if (root->left) level(root->left, depth + 1, res);//递归处理右子树if (root->right) level(root->right, depth + 1, res);}
};

迭代解法

同 #102 题解法,最终只需要将结果逆序输出即可。

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> res;if (root == nullptr) return res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int levelSize = q.size();vector<int> currentLevel;for (int i = 0; i < levelSize; ++i) {TreeNode* node = q.front();q.pop();currentLevel.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}res.push_back(currentLevel);}//反转结果,从底部到顶部reverse(res.begin(), res.end());return res;}};

LeetCode #429:N-ary Tree Level Order Traversal - N 叉树的层序遍历

#429
给定一个 N 叉树,返回其节点值的层序遍历。 树的序列化输入是用层序遍历,每组子节点都由 null 值分隔。

与处理二叉树类似,我们依然利用队列保存每一层的所有节点,把队列里的所有节点弹出队列,然后把这些节点各自的子节点入队列

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {//如果根节点为空,则直接返回一个空的二维向量if (!root) return {};//存储层序遍历的结果vector<vector<int>> res;queue<Node*> q;//将根节点入队q.push(root);//当队列不为空时,进行循环遍历while (!q.empty()) {//获取当前层的节点数,即队列的大小int levelSize = q.size();//存储当前层的所有节点值vector<int> currentLevel;//遍历当前层的所有节点for (int i = 0; i < levelSize; ++i) {//从队列中取出当前节点Node* cur = q.front();q.pop();//将当前节点的值添加到 currentLevel 向量中currentLevel.push_back(cur->val);//遍历当前节点的所有子节点,并将它们入队for (Node* child : cur->children) q.push(child);}//将当前层的节点值向量添加到 res 中res.push_back(move(currentLevel));   //注意这里使用了 move(),以优化性能}//返回层序遍历的结果return res;}
};

该算法的时间复杂度为 O ( n ) \ O(n)  O(n),空间复杂度为 O ( n ) \ O(n)  O(n)

LeetCode #637:Average of Levels in Binary Tree 二叉树的层平均值

#637
给定一个非空二叉树的根节点 root ,以数组的形式返回每一层节点的平均值

广度优先搜索(BFS)

从根节点开始搜索,每一轮遍历同一层的全部节点,记录该层的节点总值和节点数,求该层平均值加入 res 结果集中,直至完全遍历整棵二叉树。

借鉴层序遍历的做法,我们可以使用队列存储待访问节点,只要确保在每一轮遍历时,队列中的节点是同一层的全部节点即可

首先,初始化队列和结果集,将根节点入队列:

vector<double> res;
queue<TreeNode*> q;
q.push(root);

每一轮遍历时,将队列中的节点全部弹出,记录这些节点的数量以及它们的节点值之和,并计算这些节点的平均值,然后将这些节点的全部非空子节点加入队列,重复上述操作直到队列为空,遍历结束;同时,我们在每一轮遍历之前获得队列中的节点数量 levelSize ,遍历时只遍历 levelSize 个节点,即可满足每一轮遍历的是同一层的全部节点。

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<double> res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {double sum = 0;int levelSize = q.size();for (int i = 0; i < levelSize; i++) {TreeNode* node = q.front();q.pop();//对每层节点求和sum += node->val;//加入非空子节点TreeNode* left = node->left, *right = node->right;//为避免定义变量类型失误,可以考虑如下写法:// auto left = node->left, right = node->right;if (left != nullptr) q.push(left);if (right != nullptr) q.push(right);}//计算每层节点值的平均值res.push_back(sum / levelSize);}return res;}
};

该算法的时间复杂度为 O ( n ) \ O(n)  O(n) ,需要维护一个队列,空间复杂度为 O ( n ) \ O(n)  O(n)

深度优先搜索(DFS)

我们维护两个数组,count 用于存储二叉树的每一层的节点数,sum 用于存储二叉树的每一层的节点值之和。搜索过程中记录递归深度 depth ,检查当前层数depth 是否已经存在于 sumcount 中,如果访问到的节点在第 i 层,则count[i] 的值自增,并将该节点的值添加到 sum[i] ;如果当前层数大于 sum.size() ,说明进入了新的层,就在 sumcount 的末端添加新的元素,分别初始化当前节点的值为 1 。

遍历结束之后,i 层的平均值即为 sum[i] / count[i]

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<int> count;vector<double> sum;//遍历树,并更新每一层的节点数量以及值的总和dfs(root, 0, count, sum);//存储每一层的平均值vector<double> res;//遍历 sum 和 count 向量,计算每一层的平均值并添加到 res 中int size = sum.size();for (int i = 0; i < size; i++) res.push_back(sum[i] / count[i]);return res;}private:void dfs(TreeNode* root, int depth, vector<int> &count, vector<double> &sum) {// base caseif (root == nullptr) return;//如果当前层数小于 sum 和 count 的大小,则更新该层的节点值总和以及节点数量if (depth < sum.size()) {sum[depth] += root->val;count[depth]++;} else {//如果当前层数大于 sum 和 count 的大小,说明遇到了新的层,需要添加新的元素sum.push_back(1.0 * root->val);   //注意这里将值转换为 double 类型count.push_back(1);}//递归地对左子树进行深度优先搜索,层数加 1dfs(root->left, depth + 1, count, sum);//递归地对右子树进行深度优先搜索,层数也加 1dfs(root->right, depth + 1, count, sum);}
};

呜啊?

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/400549.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

python结合csv和正则实现条件筛选数据统计分数

前景提要&#xff1a; 有一个项目的数值和员工统计的对不上&#xff0c;如果一页一页翻找自己手动算&#xff0c;一个就有16、7页&#xff0c; 功能实现 1、创建csv文件 需要将每一个模块的所有数据头提取出来&#xff0c;这个可以直接用爬虫或者手工复制出来&#xff0c;因…

The Sandbox 游戏制作教程第 4 章|使用装备制作游戏,触发独特互动

欢迎回到我们的系列&#xff0c;我们将记录 The Sandbox Game Maker 的 “On-Equip”&#xff08;装备&#xff09;功能的多种用途。 如果你刚加入 The Sandbox&#xff0c;On-Equip 功能是 “可收集组件”&#xff08;Collectable Component&#xff09;中的一个多功能工具&a…

无人机的电压和放电速率,你知道吗?

一、无人机电压 无人机电瓶多采用锂电池&#xff0c;其电压范围在3.7伏至44.4伏之间&#xff0c;具体取决于电池的单体电压和串联的电池节数。 单体电压&#xff1a;锂电池的单体电压通常为3.7V&#xff0c;但在满电状态下可能达到4.2V。 串联电池节数&#xff1a;无人机电瓶…

Java面试八股之消息队列通常由哪些角色组成

消息队列通常由哪些角色组成 消息队列系统通常涉及几个核心角色&#xff0c;这些角色协同工作以实现消息的传递和处理。主要的角色包括&#xff1a; 生产者&#xff08;Producer&#xff09;&#xff1a; 生产者是消息的创建者&#xff0c;负责将消息发送到消息队列中。生产者…

基于RK3568 Android11 移除长按电源按键弹窗的对话框中的 [关机] 和 [紧急呼救] 选项(详细分析)

一般来说&#xff0c;与Android按键窗口事件相关的基本是与frameworks/base/services/core/java/com/android/server/policy/PhoneWindowManager.java 这个文件有关。   因此先打开与输入相关的日志&#xff0c;如下&#xff1a;   然后重新编译烧录后查看打印的日志可以看…

基于Python、Django开发Web计算器

1、创建项目 创建Django项目参照https://blog.csdn.net/qq_42148307/article/details/140798249&#xff0c;其中项目名为compute&#xff0c;并在该项目下创建一个名为app的应用&#xff0c;并且进行基本的配置。 2、导入Bootstrap前端框架 Bootstrap的使用参照https://blo…

uvm(7)factory

重载 针对任务或者函数&#xff0c;定义virtual;然后就可以重载 第二个是 约束的重载 然后 m_trans.crc_err_cons.constraint_mode(0); 这个是关闭此约束 m_trans.constraint_mode(0); 这是关闭所有约束 还可以集成原来的transation直接重写约束起到重载的作用 用factory重…

【数据结构】二叉树(一)

目录 1. 树型结构 概念 树的表示形式 ​编辑 2. 二叉树&#xff08;重点&#xff09; 2.1 概念 2.2 二叉树的性质 2.3 二叉树的存储 2.4 二叉树的遍历 前中后序遍历 层序遍历&#xff1a; 2.5二叉树的基本操作 本篇主要理解树和二叉树相关概念&#xff0c;二叉树遍…

0813,引用,函数重载,内存布局叭叭叭

是我4句话5个ERROR&#xff0c;阿巴阿巴 001_arrpointer.cc #include <iostream> using std::cout; using std::endl;void test(){int a[5]{1,2,3,4,5};int (*p)[5]&a;cout<<p<<endl;cout<<p1<<endl;int *pp(int*)(&a1);//第二个数组的…

vue 获取当前页面路由

vue2 &#xff1a; import { getCurrentInstance } from ‘vue’; //获取当前页路由 data() { return { currentRouter: ‘’,//默认路由 } } const { proxy } getCurrentInstance(); this.currentRouter proxy.$router.currentRoute.meta.title vue3 &#xff1a; import …

机器学习之随机森林

文章目录 1. 随机森林概述1.1 定义与起源1.2 与其他算法的比较 2. 随机森林的工作原理2.1 决策树基础2.2 Bagging机制2.3 随机性的引入 3. 随机森林的构建过程3.1 数据准备3.2 特征选择3.3 多棵树的集成 4. 随机森林的优缺点分析4.1 优势4.2 局限性 5. 随机森林的应用场景5.1 分…

Go调度器

线程数过多,意味着操作系统会不断地切换线程,频繁的上下文切换就成了性能瓶颈.Go提供一种机制 可以在线程中自己实现调度,上下文切换更轻量,从而达到线程数少,而并发数并不少的效果,而线程中调度的就是Goroutine 调度器主要概念: 1.G:即Go协程,每个go关键字都会创建一个协程…

Vulnhub JIS-CTF靶机详解

项目地址 https://www.vulnhub.com/entry/jis-ctf-vulnupload,228/https://www.vulnhub.com/entry/jis-ctf-vulnupload,228/ 修改靶机的网卡 开机时长按shift&#xff0c;进入此页面 选择root模式进入 将只读模式改为读写模式 mount -o remount,rw / 查看本机的网卡名称 …

C语言进阶(9)

程序的执行时有两种环境&#xff0c;一种是翻译环境&#xff0c;另一种是执行环境。程序先经过编译成为obj的后缀的文件&#xff0c;然后将文件和链接库链接起来&#xff0c;然后将形成可执行程序&#xff0c;前者时翻译环境&#xff0c;后者时执行环境。(链接库就是库函数的所…

C语言——构造类型

构造类型 数据类型分类 结构体 结构体的定义 定义&#xff1a;自定义数据类型的一种&#xff0c;关键字 struct &#xff0c;结构体类型的变量可以存储多个不同数据类型的数据。 定义格式&#xff1a; struct 结构体名 { 数据类型1 成员名称1; 数据类型2 成员名称2; … } 注…

element-plus的表单输入框有清除按钮的,文字输入前后宽度不一致怎么解决

输入内容之后多了一个可清除的图标&#xff0c;输入框的宽度也被撑开了 根据输入前后的dom对比发现&#xff0c;多了一个图标的span标签 :deep(.el-input__wrapper) {position: relative;.el-input__inner {padding-right: 18px;}.el-input__suffix {position: absolute;right:…

【qmake: No such file or directory 的问题解决最全】

尝试1 qmake: could not exec ‘/usr/lib/x86_64-linux-gnu/qt4/bin/qmake’: No such file or directory 执行 qmake -v出现错误&#xff1a;qmake: could not exec ‘/usr/lib/x86_64-linux-gnu/qt4/bin/qmake’: No such file or directory 分析&#xff1a; qtchooser默…

【简历】北京某985大学:JAVA秋招简历指导,面试通过率较高

注&#xff1a;为保证用户信息安全&#xff0c;姓名和学校等信息已经进行同层次变更&#xff0c;内容部分细节也进行了部分隐藏 简历说明 我们今天要看一位来自25届985同学的JAVA简历。 既然要参加校招的话&#xff0c;我们校招法典的第一准则&#xff1a;定你的学校层次。 …

Java面试八股之什么是消息队列

什么是消息队列 消息队列&#xff08;Message Queue&#xff09;是一种应用程序间通信&#xff08;IPC&#xff09;的形式&#xff0c;它允许进程将消息发送到另一个消息队列&#xff0c;接收端则可以在任何时刻从队列中取出这些消息进行处理。消息队列提供了一种异步处理、解…