当前位置: 首页 > 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异步…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...