剑指offer——JZ34 二叉树中和为某一值的路径(二) 解题思路与具体代码【C++】

一、题目描述与要求

二叉树中和为某一值的路径(二)_牛客题霸_牛客网 (nowcoder.com)

题目描述

输入一颗二叉树的根节点root和一个整数expectNumber,找出二叉树中结点值的和为expectNumber的所有路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点,不能从子节点到父节点

4.总节点数目为n

如二叉树root为{10,5,12,4,7},expectNumber为22

则合法路径有[[10,5,7],[10,12]]

数据范围:

树中节点总数在范围 [0, 5000] 内

-1000 <= 节点值 <= 1000

-1000 <= expectNumber <= 1000

示例

示例1:

输入:{10,5,12,4,7},22

返回值:[[10,5,7],[10,12]]

说明:返回[[10,12],[10,5,7]]也是对的

示例2:

输入:{10,5,12,4,7},15

返回值:[]

示例3:

输入:{2,3},0

返回值:[]

示例4:

输入:{1,3,4},7

返回值:[]


二、解题思路

根据题目描述,我们需要找到二叉树中结点值的和为target的所有路径。

路径定义为从树的根结点开始往下一直到叶子结点所经过的结点,因而我们需要从根结点开始遍历所有结点一直到叶子结点的所有路径,并且判断其是否满足target,而我们怎么去实现遍历完一条分支之后转移到另一条分支呢?那就是回溯,也就是当我们访问完当前这一条路径并且到达叶子结点的时候,我们返回上一个结点,去访问另一个分支,这样就能够找出所有的路径。

这一思路也就是遍历图的深度优先算法思想。

首先我们定义两个vector,一个用来存储符合题目要求的所有路径,另一个用来存储目前所走的路径,需要设置为全局变量,因为dfs函数时另外写的,方便访问,而不用通过传参;

然后我们调用dfs函数来寻找路径。

首先先判断是否为空树/空节点,是的话就返回空/返回上一级;

然后就是将当前结点存入path中,这里用emplace_back/push_back都可以,emplace_back的效率会更高一点;

然后更新目前的目标值,也就是减去当前结点的值;

然后判断当前结点是否为叶子结点,如果是的话判断此时的target是否等于0,如果以上条件都满足的话就说明当前路径是满足条件的路径,将路径存入v中,否则则对当前结点的左右子树继续进行遍历;

每遍历完一条分支之后,都需要回溯到上一个结点,从而去访问另一条分支,因而需要将当前结点弹出;

最后返回v即可。


三、具体代码

#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param root TreeNode类 * @param target int整型 * @return int整型vector<vector<>>*/vector<vector<int>> v;//存储所有路径vector<int> path;//存储当前路径void dfs(TreeNode* root,int target){//如果为空树,返回空if(root==nullptr)  return;//emplace_back——就地构造(直接在容器内构造对象,不用拷贝一个复制品再使用)+强制类型转换) 比push_back效率更高//路径更新 添加当前结点path.emplace_back(root->val);//更新目标值 减去当前结点的值target-=root->val;//如果当前结点为叶子结点,且目前的目标值=0,则代表是满足的路径if(root->left==nullptr&&root->right==nullptr&&target==0){v.emplace_back(path);}dfs(root->left,target);dfs(root->right,target);//遍历到叶子结点之后,弹出当前结点,寻找另一条路径//也就是当前分支结束后,回溯到上一级沿另一个分支继续走到底 一直到所有结点都被访问过path.pop_back();}vector<vector<int> > FindPath(TreeNode* root, int target) {dfs(root,target);return v;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/151294.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Youtube视频下载工具分享-油管视频,音乐,字幕下载方法汇总

YouTube视频下载方法简介 互联网上存在很多 YouTube 下载工具&#xff0c;但我们经常会发现自己收藏的工具没过多久就会失效&#xff0c;我们为大家整理的这几种方法&#xff0c;是存在时间较久并且亲测可用的。后续如果这些工具失效或者有更好的工具&#xff0c;我们也会分享…

c++day2

1.XMIND 2. 自己封装一个矩形类(Rect)&#xff0c;拥有私有属性:宽度(width)、高度(height)&#xff0c;定义公有成员函数: 初始化函数:void init(int w, int h) 更改宽度的函数:set_w(int w) 更改高度的函数:set_h(int h) 输出该矩形的周长和面积函数:void show() #include &…

基于SSM的固定资产管理系统的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…

网站强制跳转至国家反诈中心该怎么办?怎么处理?如何解封?

在互联网环境中&#xff0c;网站安全是非常重要的。然而&#xff0c;在实际操作过程中&#xff0c;不少网站可能因内容问题、技术安全漏洞等原因被迫下线甚至跳转至国家反诈骗中心网址。面对这一严峻问题&#xff0c;我们如何有效解决&#xff0c;让网站恢复运行并解除强制跳转…

点餐小程序实战教程06-首页开发

用户注册功能开发好了之后&#xff0c;我们就要开发小程序&#xff0c;首先我们是规划小程序的功能模块&#xff0c;我们一共是四个模块&#xff0c;分别是首页、订单、消息和我的。 首页我们主要是点餐的功能&#xff0c;可以选择菜品&#xff0c;加入到购物车&#xff0c;然…

【C++】stack/queue/deque

目录 一、stack 1.1 stack的接口 1.2 关于使用stack的例题 1.2.1 最小栈 1.2.2 栈的压入、弹出序列 1.2.4 逆波兰表达式求值 1.3 stack的模拟实现 二、queue 2.1 queue的接口 2.2 queue的模拟实现 三、deque 3.1 deque底层实现原理 3.1.1 头插实现原理 3.1.2 尾插…

Cocos Creator3.8 项目实战(五)背景无限滚屏效果如何实现

在游戏中&#xff0c;我们经常会实现背景无限滚动的效果。那这些效果是怎么实现的呢&#xff1f; 原理很简单&#xff0c;就是使用多张背景图&#xff0c;每张图&#xff0c;每一帧都同时移动&#xff0c;当图移出屏幕外时&#xff0c;将其位置设置到下一张图的初始位置&#x…

加速attention计算的工业标准:flash attention 1和2算法的原理及实现

transformers目前大火&#xff0c;但是对于长序列来说&#xff0c;计算很慢&#xff0c;而且很耗费显存。对于transformer中的self attention计算来说&#xff0c;在时间复杂度上&#xff0c;对于每个位置&#xff0c;模型需要计算它与所有其他位置的相关性&#xff0c;这样的计…

10.8c++作业

#include <iostream>using namespace std; class Rect {int width; //宽int height; //高 public://初始化函数void init(int w,int h){widthw;heighth;}//更改宽度void set_w(int w){widthw;}//更改高度void set_h(int h){heighth;}//输出矩形周长和面积void show(){co…

【ORACLE】ORA-00972:标识符过长

问题 执行创建表结构sql&#xff0c;提示 ORA-00972&#xff1a;标识符过长&#xff1b; 如图所示&#xff0c;约束名称超过30个字符了 原因 一、11G and before 在使用11G数据库时&#xff0c;经常会遇到报错ORA-00972&#xff0c;原因是因为对象名称定义太长&#xff0c…

C++——继承

什么是继承 继承是两个类之间的关系&#xff0c;可以实现派生类&#xff08;子类&#xff09;对基类&#xff08;父类&#xff09;的复用&#xff0c;即派生类在基类的基础上进行扩展&#xff0c;实现更多功能。例如学生和人这两个对象就可以是继承关系&#xff0c;学生具有人…

基于Dockerfile搭建LNMP

目录 一、基础环境准备 1、环境前期准备 二、部署nginx&#xff08;容器IP 为 172.18.0.10&#xff09; 1、配置Dockerfile文件 2、配置nginx.conf文件 3、构建镜像、启动镜像 三、部署mysql 1、配置Dockerfile文件 2、配置my.conf文件 3、构建镜像、启动镜像 5、验…

【Linux】Vim使用总结

【Linux】Vim使用总结 Vim 的三种模式命令行模式1. 移动2.复制&#xff0c;粘贴&#xff0c;剪切3.撤销4.大小写切换&#xff0c;替换&#xff0c;删除 插入模式底行模式 Vim 的三种模式 一进入VIM就是处于一般模式&#xff08;命令模式&#xff09;&#xff0c;该模式下只能输…

flink双流join结果数据重复问题排查

1.背景 Kafka的两个topic&#xff0c;topic1 为用户下单明细记录&#xff08;包含订单基本信息&#xff09;&#xff0c;topic2为下单渠道记录&#xff08;包含下单来源和渠道内容设备相关的信息&#xff09; &#xff0c;要求实时统计每分钟内所有订单下的渠道来源分布详情。具…

使用Windows系统自带的安全加密解密文件操作步骤详解

原以为安全加密的方法是加密压缩包&#xff0c;有的需要用软件加密文件&#xff0c;可每次想往里面修改或存放文件都要先解密&#xff0c;不用时&#xff0c;还得去加密&#xff0c;操作步骤那么多&#xff0c;那多不方便呀&#xff0c;这里讲讲用系统自带的BitLocker加密工具怎…

【SQL】MySQL中的约束

1. 主键约束&#xff08;primary key&#xff09;&#xff1a; 相当于唯一约束非空约束分为单列主键&#xff0c;多列联合主键&#xff0c;一个表只有一个主键多列联合主键的每列都不能为空 2. 自增长约束&#xff08;auto_increment&#xff09;&#xff1a; 用在单列主键后…

Acwing.889 满足条件的01序列

题目 给定n个0和n个1&#xff0c;它们将按照某种顺序排成长度为2n的序列&#xff0c;求它们能排列成的所有序列中&#xff0c;能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。 输出的答案对109&#xff0b;7取模。 输入格式 共一行&#xff0c;包含整数n。 …

10_8C++

X-Mind #include <iostream>using namespace std; class Rect { private:int width;int heigjt; public:void init(int w,int h){width w;heigjt h;}void set_w(int w){width w;}void set_h(int h){heigjt h;}void show(){cout << "矩形的周长" <…

day10.8ubentu流水灯

流水灯 .text .global _start _start: 1.设置GPIOE寄存器的时钟使能 RCC_MP_AHB4ENSETR[4]->1 0x50000a28LDR R0,0X50000A28LDR R1,[R0] 从r0为起始地址的4字节数据取出放在R1ORR R1,R1,#(0x1<<4) 第4位设置为1STR R1,[R0] 写回2.设置PE10管脚为输出模式 G…

okhttp4.11源码分析

目录 一&#xff0c;OKHTTP时序图 二&#xff0c;OKHTTP类图 三&#xff0c;OKHTTP流程图 一&#xff0c;OKHTTP时序图 上图是整个okhttp一次完整的请求过程&#xff0c;时序图里面有些部分为了方便采用了简单的描述&#xff0c;描述了主要的流程&#xff0c;细节的话&#…