当前位置: 首页 > news >正文

数据结构(六)—— 二叉树(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 递归回溯&#xff1a;回溯是递归的副产品&#xff0c;只要有递归就会有回溯 首先考虑深度优先搜索&#xff1b;而题目要求从根节点到叶子的路径&#xff0c;所以需要前序…...

JVM基础知识(一)

1.整体架构和组件 1.Class Loader Class Loader&#xff08;类加载器&#xff09;负责将.class文件加载到JVM中&#xff0c;并生成对应的Java类对象&#xff08;Class对象&#xff09;。Java中有三种类加载器&#xff1a; Bootstram ClassLoader&#xff1a;加载核心类库&…...

ASP.NET Core Web API用户身份验证

一、JWT介绍 ASP.NET Core Web API用户身份验证的方法有很多&#xff0c;本文只介绍JWT方法。JWT实现了服务端无状态&#xff0c;在分布式服务、会话一致性、单点登录等方面凸显优势&#xff0c;不占用服务端资源。简单来说&#xff0c;JWT的验证过程如下所示&#xff1a; &a…...

785. 快速排序

785. 快速排序 给定你一个长度为 n n n 的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行&#xff0c;第一行包含整数 n n n。 第二行包含 n n n 个整数&#xff08;所有整数均在 1 ∼ 1 0 9 1 \th…...

C6678学习-IPC

文章目录 1、简介2、模块MultiProc静态设置&#xff08;cfg设置&#xff09;动态设置 IPCNotifyMessageQShareRegion 1、简介 IPC: Inter-Processor Communication 处理器间通信&#xff0c;指提供多处理器环境中的处理器之间的通信、相同处理器不同线程间的通信。包括数据传递…...

利用 Delte-Sigma ADC简化电路设计

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

如何在 Windows 11 启用 Hyper-V

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

哈希表企业应用-DNA的字符串检测

DNA的字符串检测-引言 若干年后, ikun DNA 检测部成立,专门对 这些ikun的解析检测 突然发现已经完全控制不了 因为学生已经会了 而且是太会了 所以DNA采用 以下视频测试: ikun必进曲 ikun必经曲 ikun必阶曲 如何感受到了吧!,如果你现在唱跳并且还Rap 还有打篮球 还有铁山靠 那…...

Kafka运维与监控

Kafka运维与监控 Kafka运维与监控一、简介二、运维1.安装和部署安装部署 2.优化参数配置配置文件高级配置分区和副本设置分区数量设置副本数量设置 网络参数调优传输机制设置连接数和缓冲区大小设置 消息压缩和传输设置消息压缩设置消息传输设置 磁盘设置和文件系统分区磁盘容量…...

【Redis—哨兵机制】

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

MySQL学习笔记第七天

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

中级软件设计师备考---程序设计语言和法律法规知识

目录 需要掌握的程序语言特点法律法规知识---保护期限法律法规知识---知识产权人确定法律法规知识---侵权判定标准化基础知识 需要掌握的程序语言特点 Fortran语言&#xff1a;科学计算、执行效率高Pascal语言&#xff1a;为教学而开发的、表达能力强&#xff0c;演化出了Delp…...

Leetcode434. 字符串中的单词数

Every day a leetcode 题目来源&#xff1a;434. 字符串中的单词数 解法1&#xff1a;istringstream 我们知道&#xff0c;C默认通过空格&#xff08;或回车&#xff09;来分割字符串输入&#xff0c;即区分不同的字符串输入。 istringstream类用于执行C风格的串流的输入操…...

C++ cmake工程引入qt6和Quick 教程

目录标题 前言QML简介锻炼C水平 cmake修改方法方式一&#xff08;qt6_add_resources&#xff09;方式二 (qt_add_qml_module ) 其他相关知识为什么会有_other_files&#xff1f;qt_standard_project_setup() 函数qt_add_qml_module() 和 qt6_add_resources()的方式差异const QU…...

JavaEE - 网络编程

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

【Android车载系列】第11章 系统服务-SystemServer自定义服务

1 编写自定义系统服务 1.1 AIDL接口定义 系统源码目录/frameworks/base/core/java/android/app/下新建AIDL接口IYvanManager.aidl package android.app;/** * 目录&#xff1a;/frameworks/base/core/java/android/app/IYvanManager.aidl */ interface IYvanManager{String …...

Lerna

Lerna Lerna是一个优化基于gitnpm的多pagkage项目的管理工具 解决的痛点 痛点一:重复操作 多Package本地link多Package依赖安装多Package单元测试多Package代码提交多Package代码发布 痛点二:版本一致性 发布时版本一 致性发布后相互依赖版本升级 package越多&#xff0c;管…...

迁移学习 pytorch

迁移学习(Transfer Learning)是通过使用一个预训练模型来快速训练一个新的网络模型,通常应用于数据集较小或计算资源较少的情况下。在 PyTorch 中,由于 torchvision 库中已经内置了一些经典的预训练模型,因此我们可以通过简单的调用函数来实现迁移学习。 下面是一个基于 …...

【python】keras包:深度学习( RNN循环神经网络 Recurrent Neural Networks)

RNN循环神经网络 应用&#xff1a; 物体移动位置预测、股价预测、序列文本生成、语言翻译、从语句中自动识别人名、 问题总结 这类问题&#xff0c;都需要通过历史数据&#xff0c;对未来数据进行预判 序列模型 两大特点 输入&#xff08;输出&#xff09;元素具有顺序关系…...

vue框架快速入门

vue 1、第一个Vue程序1.1、什么是Vue程序1.2、为什么要使用MVVM1.3、Vue1.4、第一个vue程序 2、基础语法2.1、v-bind2.2、v-if&#xff0c; v-else2.3、v-for2.4、v-on 3、Vue表单双绑、组件3.1、什么是双向数据绑定3.2、在表单中使用双向数据绑定3.3、什么是组件 4、Axios异步…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

欢乐熊大话蓝牙知识17:多连接 BLE 怎么设计服务不会乱?分层思维来救场!

多连接 BLE 怎么设计服务不会乱&#xff1f;分层思维来救场&#xff01; 作者按&#xff1a; 你是不是也遇到过 BLE 多连接时&#xff0c;调试现场像网吧“掉线风暴”&#xff1f; 温度传感器连上了&#xff0c;心率带丢了&#xff1b;一边 OTA 更新&#xff0c;一边通知卡壳。…...