【二叉树算法题记录】二叉树的所有路径,路径总和——回溯
目录
- 257. 二叉树的所有路径
- 题目描述
- 题目分析
- cpp代码
- 112. 路径总和
- 题目描述
- 题目分析
- cpp代码
257. 二叉树的所有路径
题目描述
给你一个二叉树的根节点root ,按任意顺序,返回所有从根节点到叶子节点的路径。
题目分析
其实从根节点往下走,遍历的思路就如下图所示。我们先走到叶子节点(这是一条路径),然后再往上回溯,如果回溯到的上层节点有右孩子,那么就再按照右边的路径往下走(另一条路径)。

- 递归传入参数及返回值
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result)
cur是当前节点,path用来记录当前路径,result是最终返回的结果。
- 递归终止条件
当我们遍历到叶子节点时,就要把当前路径path加入result了。
if(cur->left == NULL && cur->right == NULL) {// 如果当前节点是叶子节点,也就是左右孩子都为空// 也就是说已经遍历了一条根节点到叶子节点的路径// 我们要把这条路径放进result中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;}
- 单层递归逻辑
我们进行的是一个前序遍历,但是需要注意的是当前节点的处理要在递归终止条件之前进行:
path.push_back(cur->val); // 先将当前节点放进当前path中,再判断结束条件
这是因为所有节点包括叶子节点都要加入path,如果先判断终止,再处理当前节点则会漏掉叶子节点。
在进行左右孩子的遍历时,我们要注意判断节点是否为空:
if(cur->left) {traversal(cur->left, path, result);path.pop_back(); // 回溯}if(cur->right) {traversal(cur->right, path, result);path.pop_back(); // 回溯}
cpp代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void traversal(TreeNode* cur, vector<int>& path, vector<string>& result){path.push_back(cur->val); // 先将当前节点放进当前path中,再判断结束条件if(cur->left == NULL && cur->right == NULL) {// 如果当前节点是叶子节点,也就是左右孩子都为空// 也就是说已经遍历了一条根节点到叶子节点的路径// 我们要把这条路径放进result中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(); // 回溯}}vector<string> binaryTreePaths(TreeNode* root) {vector<int> path;vector<string> result;if(root == NULL) return result;traversal(root, path, result);return result;}
};
112. 路径总和
题目描述
给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和targetSum。如果存在,返回true;否则,返回false。
题目分析
其实这题跟上题是一样的,只不过这里多了一个targetSum的判断。
cpp代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void traversal(TreeNode* cur, vector<int>& path, vector<int>& sum){path.push_back(cur->val);if(cur->left == NULL && cur->right == NULL) {cout << "当前路径: ";for(int p : path) {cout << p << ' ';}cout << endl;sum.push_back(accumulate(path.begin(), path.end(), 0));cout << "当前路径总和: " << accumulate(path.begin(), path.end(), 0) << endl;return;}if(cur->left) {traversal(cur->left, path, sum);path.pop_back();}if(cur->right) {traversal(cur->right, path, sum);path.pop_back();}}bool hasPathSum(TreeNode* root, int targetSum) {vector<int> path;vector<int> sum;if(root == NULL) return false;traversal(root, path, sum);if(find(sum.begin(), sum.end(), targetSum) == sum.end()){return false;}else return true;}
};
相关文章:
【二叉树算法题记录】二叉树的所有路径,路径总和——回溯
目录 257. 二叉树的所有路径题目描述题目分析cpp代码 112. 路径总和题目描述题目分析cpp代码 257. 二叉树的所有路径 题目描述 给你一个二叉树的根节点root ,按任意顺序,返回所有从根节点到叶子节点的路径。 题目分析 其实从根节点往下走,…...
verilog基础语法之数据类型
verilog基础语法之数据类型 1、 wire类型2、 reg类型3、向量 Verilog最常用的数据类型有两种:线网(wire)和寄存器(reg)。其中,wire 类型表示硬件单元之间的物理连线,reg用来表示存储单元。 1、…...
ansible部署lamp架构
搭建参考:ansible批量运维管理-CSDN博客 定义ansible主机清单 [rootansible-server ~]# vim /etc/hosts 192.168.200.129 host01 192.168.200.130 host02 [rootansible-server ~]# vim /etc/ansible/hosts [webserver] host01 host02 在ansible端编写index.html…...
Java面试——MyBatis
优质博文:IT-BLOG-CN 一、MyBatis 与 JDBC 的区别 【1】JDBC 是 Java 提供操作数据库的 API;MyBatis 是一个持久层 ORM 框架,底层是对 JDBC 的封装。 【2】使用 JDBC 需要连接数据库,注册驱动和数据库信息工作量大,每…...
Ubuntu-22.04使用systemd.mount挂载本地磁盘
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、systemd.mount是什么?二、使用步骤1.增加mount文件2.测试mount文件 三、补充说明总结 前言 挂载磁盘方式我们都知道很多人喜欢在/etc/fstab里面…...
【Qt】界面定制艺术:光标(cursor)、字体(font)、提示(toolTip)、焦点(focusPolicy)与样式表(styleSheet)的深度探索
文章目录 前言:1. cursor: 设置按钮的光标2. front:设置字体3. toolTip: 鼠标悬停提示4. focusPolicy:设置控件获取到焦点的策略5. styleSheet : 样式表总结: 前言: 在现代软件开发中,用户界面(UI)的设计和…...
Python GraphQL服务器实现库之tartiflette使用详解
概要 Tartiflette是一个为Python编写的GraphQL服务器实现,它建立在现代异步编程库如asyncio之上,提供了高性能的GraphQL执行环境。Tartiflette专注于提供最佳的开发者体验,支持最新的GraphQL特性。 安装 安装Tartiflette相对简单,但需要依赖于一些系统级的库。 首先,需…...
面试官:请介绍类加载过程,什么是双亲委派模型?
🚀类加载过程是指在 Java 程序运行时,将类的字节码文件加载到内存中并转换为 Class 对象的过程。Java 类加载器负责加载类,其主要任务是在运行时查找和装载类文件,以生成对应的 Class 对象。 Java的类加载过程一般可以分为以下几个…...
mysql 细分
索引选择性 索引列的唯一值数量 / 表中的总行数 mysql如何优化-CSDN博客 批量问题 批处理默认是逐条发送 SQL 到数据库的,没有充分利用数据库提供的原生批处理能力,需要额外的配置来启用真正的批处理支持,如使用ExecutorType.BATCH 自定…...
数据驱动实战二
目标 掌握数据驱动的开发流程掌握如何读取JSON数据文件巩固PO模式 1. 案例 对TPshop网站的登录模块进行单元测试 1.1 实现步骤 编写测试用例采用PO模式的分层思想对页面进行封装编写测试脚本定义数据文件,实现参数化 1.2 用例设计 1.3 数据文件 {"login…...
解决参考文献自动生成标号,换行时自动缩进
问题如下图所示,红色方框部分应该填充内容,但自动生成标号时不会填充: 解决方案: 1. 选中内容: 2. 找到布局-段落: 3. 选择“无”,即可。...
网络安全专业岗位详解+自学学习路线图
很多网安专业同学一到毕业就开始迷茫,不知道自己能去做哪些行业?其实网络安全岗位还是蛮多的,下面我会介绍一些网络安全岗位,大家可以根据自身能力与喜好决定放哪个方向发展。 渗透测试/Web安全工程师 主要是模拟黑客攻击&#…...
mybatisPlus一个事务中切换数据源概述
概述 在多数据源的配置下,业务中经常遇到在一个被本地事务包裹的save/edi方法中需要查询另一个数据源的数据; 直接查询会提示table不存在,这是因为一个事务和一个mysql连接是绑定的,mysql的连接背后包含了数据库信息,…...
如何在Android手机上恢复已删除的视频?
有时,由于不同的原因,可能会发生意外的数据丢失灾难。 那么如何在Android手机内存或没有计算机的情况下恢复已删除的视频呢?本文将给你一个答案。 如何在Android上恢复已删除的视频? 不要惊慌!您可以在Android手机上恢…...
【项目实战】使用Github pages、Hexo如何10分钟内快速生成个人博客网站
文章目录 一.准备工作1.安装git2.安装node安装 cnpm 3.使用 GitHub 创建仓库,并配置 GitHub Pages0.Github Pages是什么1. 在 GitHub 上创建一个新仓库2. 创建您的静态网站3. 启用 GitHub Pages4. 等待构建完成5. 访问您的网站 二. Hexo1.什么是Hexo2.安装Hexo1. 安…...
大数据中服役新数据节点和退役旧节点步骤(hive,hadoop)
1- 节点上线操作 当要新上线数据节点的时候 ,需要把数据节点的名字追加在 dfs.hosts (1)关闭新增节点的防火墙 (2)在 NameNode 节点的 hosts 文件中加入新增数据节点的 hostname (3)在每个新…...
数论:不定方程的引入
研究的对象:不定方程 文章目录 研究的对象:不定方程不定方程引入:裴蜀定理证明:欧几里得算法证明:充分性证明:必要性证明: 战术总结: 不定方程引入: 不定方程࿰…...
数据中心法
数据中心法是实现词法分析器的结构化方法。通过设计主表和子表分开存储状态转移信息,实现词法分析器的控制逻辑和数据结构分离。 主要解决了状态爆炸、难以维护和复杂性的问题。 状态爆炸是指当状态和转移较多时,单一使用一个表来存储所有的信息的话会导…...
pdffactory pro8.0虚拟打印机(附注册码)
PdfFactory pro是一款非常受欢迎的PDF虚拟打印机,可以帮助用户将你的其他文档保存为PDF格式。请为用户提供打印/发送/加密等多种实用功能,以及一套完善的PDF打印方案。 使用说明 下载pdfFactory Pro压缩包,解压后,双击exe文件&am…...
处理用户输入
目录 一、传递参数 1.1 读取参数 1.2 读取脚本名 二、跟踪参数 三、移动参数 四、处理选项 4.1 查找选项 4.1.1 处理简单选项 4.1.2 分离参数和选项 4.1.3 处理含值的选项 五、选项标准化 5.1 使用 getopt 命令 5.1.1 命令格式 5.1.2 在脚本中使用getopt 5.2 使用…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
