数据结构(六)—— 二叉树(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异步…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...

多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...

elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...
数据库正常,但后端收不到数据原因及解决
从代码和日志来看,后端SQL查询确实返回了数据,但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离,并且ai辅助开发的时候,很容易出现前后端变量名不一致情况,还不报错,只是单…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架
文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理:检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目:RankRAG:Unifying Context Ranking…...
HTML中各种标签的作用
一、HTML文件主要标签结构及说明 1. <!DOCTYPE html> 作用:声明文档类型,告知浏览器这是 HTML5 文档。 必须:是。 2. <html lang“zh”>. </html> 作用:包裹整个网页内容,lang"z…...