数据结构(六)—— 二叉树(4)回溯
文章目录
- 一、题
- 1 257 二叉树的所有路径
- 1.1 写法1
- 1.2 写法2
一、题
1 257 二叉树的所有路径
1.1 写法1
递归+回溯:回溯是递归的副产品,只要有递归就会有回溯
首先考虑深度优先搜索;而题目要求从根节点到叶子的路径,所以需要前序遍历,这样才方便让父节点指向孩子节点,找到对应的路径。
递归和回溯就是一家的,本题也需要回溯。
1、确定递归函数输入输出
要传入根节点,记录每一条路径的vector<int>&
,和存放结果集的vector<string>&
,这里递归不需要返回值,
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result)
2、确定递归终止条件
一般来说都是if(cur == NULL) return,但是本题要找到叶子节点,就开始结束的处理逻辑了(把路径放进result里)。
那么什么时候算是找到了叶子节点? 是当 cur不为空,其左右孩子都为空的时候,就找到叶子节点。
if (cur->left == NULL && cur->right == NULL) { // 遇到叶子节点string sPath;for (int i = 0; i < path.size() - 1; i++) { // 将path里记录的路径转为string格式sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]); // 记录最后一个节点(叶子节点)result.push_back(sPath); // 收集一个路径return;
}
3、确定单层递归逻辑
因为是前序遍历,需要先处理中间节点,中间节点就是我们要记录路径上的节点,先放进path中。
path.push_back(cur->val);
然后是递归和回溯的过程,上面说过没有判断cur是否为空,那么在这里递归的时候,如果为空就不进行下一层递归了。
所以递归前要加上判断语句,下面要递归的节点是否为空,如下
if (cur->left) traversal(cur->left, path, result);
此时还没完,递归完,要做回溯啊,因为path 不能一直加入节点,它还要删节点,然后才能加入新的节点。
if (cur->left) {traversal(cur->left, path, result);path.pop_back(); // 回溯
}
if (cur->right) {traversal(cur->right, path, result);path.pop_back(); // 回溯
}
4、整合traversal()
class Solution {
private:void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {path.push_back(cur->val); // 中,中为什么写在这里,因为最后一个节点也要加入到path中 // 这才到了叶子节点if (cur->left == NULL && cur->right == NULL) {string sPath;for (int i = 0; i < path.size() - 1; i++) {sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]);result.push_back(sPath);return;}if (cur->left) { // 左 traversal(cur->left, path, result);path.pop_back(); // 回溯}if (cur->right) { // 右traversal(cur->right, path, result);path.pop_back(); // 回溯}}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> path;if (root == NULL) return result;traversal(root, path, result);return result;}
};
1.2 写法2
1、确定输入输出
输入:节点、每条路径string
、每条路径组成的vector<string>&
输出:空
void traversal(TreeNode* cur, string path, vector<string>& result)
注意:函数输出定义的是string
,每次都是复制赋值,没使用引用,否则就无法做到回溯的效果。(这里涉及到C++语法知识)
2、确定退出条件
if (cur->left == NULL && cur->right == NULL) {result.push_back(path);return;
}
3、确定单层逻辑
中左右
path += to_string(cur->val); // 中
... // 退出条件
if (cur->left) traversal(cur->left, path + "->", result); // 左
if (cur->right) traversal(cur->right, path + "->", result); // 右
4、整合
class Solution {
private:void traversal(TreeNode* cur, string path, vector<string>& result) {path += to_string(cur->val); // 中if (cur->left == NULL && cur->right == NULL) {result.push_back(path);return;}if (cur->left) traversal(cur->left, path + "->", result); // 左if (cur->right) traversal(cur->right, path + "->", result); // 右}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;string path;if (root == NULL) return result;traversal(root, path, result);return result;}
};
在哪儿回溯的?
如上代码貌似没有看到回溯的逻辑,其实不然,回溯就隐藏在traversal(cur->left, path + "->", result);
中的 path + "->"
。 每次函数调用完,path并没有加上"->",这就是回溯了。
使用如下代码可以更好的体会到回溯
if (cur->left) {path += "->";traversal(cur->left, path, result); // 左path.pop_back(); // 回溯 '>'path.pop_back(); // 回溯 '-'
}
if (cur->right) {path += "->";traversal(cur->right, path, result); // 右path.pop_back(); // 回溯 '>' path.pop_back(); // 回溯 '-'
}
相关文章:

数据结构(六)—— 二叉树(4)回溯
文章目录 一、题1 257 二叉树的所有路径1.1 写法11.2 写法2 一、题 1 257 二叉树的所有路径 1.1 写法1 递归回溯:回溯是递归的副产品,只要有递归就会有回溯 首先考虑深度优先搜索;而题目要求从根节点到叶子的路径,所以需要前序…...
JVM基础知识(一)
1.整体架构和组件 1.Class Loader Class Loader(类加载器)负责将.class文件加载到JVM中,并生成对应的Java类对象(Class对象)。Java中有三种类加载器: Bootstram ClassLoader:加载核心类库&…...

ASP.NET Core Web API用户身份验证
一、JWT介绍 ASP.NET Core Web API用户身份验证的方法有很多,本文只介绍JWT方法。JWT实现了服务端无状态,在分布式服务、会话一致性、单点登录等方面凸显优势,不占用服务端资源。简单来说,JWT的验证过程如下所示: &a…...
785. 快速排序
785. 快速排序 给定你一个长度为 n n n 的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行,第一行包含整数 n n n。 第二行包含 n n n 个整数(所有整数均在 1 ∼ 1 0 9 1 \th…...
C6678学习-IPC
文章目录 1、简介2、模块MultiProc静态设置(cfg设置)动态设置 IPCNotifyMessageQShareRegion 1、简介 IPC: Inter-Processor Communication 处理器间通信,指提供多处理器环境中的处理器之间的通信、相同处理器不同线程间的通信。包括数据传递…...

利用 Delte-Sigma ADC简化电路设计
很多时候在电路中选择合适的 ADC可以很大程度上简化前端的电路。这里我们一起来看一个电阻电桥的例子: 这里用到了一只仪表放大器和一只运算放大器,他们实际上主要完成了三个功能: 1. 抑制了 2.5V的共模信号; 2. 将-1…...

如何在 Windows 11 启用 Hyper-V
准备在本机玩一下k8s,需要先启用 Hyper-V,谁知道这一打开,没有 Hyper-V选项: 1、查看功能截图: 2、以下文件保存记事本,然后重命名为*.bat pushd "%~dp0" dir /b %SystemRoot%\servicing\Packa…...

哈希表企业应用-DNA的字符串检测
DNA的字符串检测-引言 若干年后, ikun DNA 检测部成立,专门对 这些ikun的解析检测 突然发现已经完全控制不了 因为学生已经会了 而且是太会了 所以DNA采用 以下视频测试: ikun必进曲 ikun必经曲 ikun必阶曲 如何感受到了吧!,如果你现在唱跳并且还Rap 还有打篮球 还有铁山靠 那…...
Kafka运维与监控
Kafka运维与监控 Kafka运维与监控一、简介二、运维1.安装和部署安装部署 2.优化参数配置配置文件高级配置分区和副本设置分区数量设置副本数量设置 网络参数调优传输机制设置连接数和缓冲区大小设置 消息压缩和传输设置消息压缩设置消息传输设置 磁盘设置和文件系统分区磁盘容量…...

【Redis—哨兵机制】
文章目录 概念哨兵机制如何工作的监控(如何判断主节点真的故障了)哪个哨兵进行主从故障转移?故障转移流程哨兵集群 概念 当进行主从复制时,如果主节点挂掉了,那么没有主节点来服务客户端的写操作请求了,也…...

MySQL学习笔记第七天
第07章单行函数 2. 数值函数 2.4 指数函数、对数函数 函数用法POW(x,y),POWER(X,Y)返回x的y次方EXP(X)返回e的x次方,其中e是一个常数,2.718281828459045LN(X),LOG(X)返回以e为底的X的对数,当x<0时,返…...

中级软件设计师备考---程序设计语言和法律法规知识
目录 需要掌握的程序语言特点法律法规知识---保护期限法律法规知识---知识产权人确定法律法规知识---侵权判定标准化基础知识 需要掌握的程序语言特点 Fortran语言:科学计算、执行效率高Pascal语言:为教学而开发的、表达能力强,演化出了Delp…...

Leetcode434. 字符串中的单词数
Every day a leetcode 题目来源:434. 字符串中的单词数 解法1:istringstream 我们知道,C默认通过空格(或回车)来分割字符串输入,即区分不同的字符串输入。 istringstream类用于执行C风格的串流的输入操…...
C++ cmake工程引入qt6和Quick 教程
目录标题 前言QML简介锻炼C水平 cmake修改方法方式一(qt6_add_resources)方式二 (qt_add_qml_module ) 其他相关知识为什么会有_other_files?qt_standard_project_setup() 函数qt_add_qml_module() 和 qt6_add_resources()的方式差异const QU…...

JavaEE - 网络编程
一、网络编程基础 为什么需要网络编程? 用户在浏览器中,打开在线视频网站,如优酷看视频,实质是通过网络,获取到网络上的一个视频资源。 与本地打开视频文件类似,只是视频文件这个资源的来源是网络。 相比本…...

【Android车载系列】第11章 系统服务-SystemServer自定义服务
1 编写自定义系统服务 1.1 AIDL接口定义 系统源码目录/frameworks/base/core/java/android/app/下新建AIDL接口IYvanManager.aidl package android.app;/** * 目录:/frameworks/base/core/java/android/app/IYvanManager.aidl */ interface IYvanManager{String …...
Lerna
Lerna Lerna是一个优化基于gitnpm的多pagkage项目的管理工具 解决的痛点 痛点一:重复操作 多Package本地link多Package依赖安装多Package单元测试多Package代码提交多Package代码发布 痛点二:版本一致性 发布时版本一 致性发布后相互依赖版本升级 package越多,管…...
迁移学习 pytorch
迁移学习(Transfer Learning)是通过使用一个预训练模型来快速训练一个新的网络模型,通常应用于数据集较小或计算资源较少的情况下。在 PyTorch 中,由于 torchvision 库中已经内置了一些经典的预训练模型,因此我们可以通过简单的调用函数来实现迁移学习。 下面是一个基于 …...

【python】keras包:深度学习( RNN循环神经网络 Recurrent Neural Networks)
RNN循环神经网络 应用: 物体移动位置预测、股价预测、序列文本生成、语言翻译、从语句中自动识别人名、 问题总结 这类问题,都需要通过历史数据,对未来数据进行预判 序列模型 两大特点 输入(输出)元素具有顺序关系…...

vue框架快速入门
vue 1、第一个Vue程序1.1、什么是Vue程序1.2、为什么要使用MVVM1.3、Vue1.4、第一个vue程序 2、基础语法2.1、v-bind2.2、v-if, v-else2.3、v-for2.4、v-on 3、Vue表单双绑、组件3.1、什么是双向数据绑定3.2、在表单中使用双向数据绑定3.3、什么是组件 4、Axios异步…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...

css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...

GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...

MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...