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

力扣——113. 路径总和

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]

示例 2:

输入:root = [1,2,3], targetSum = 5
输出:[]

示例 3:

输入:root = [1,2], targetSum = 0
输出:[]

提示:

  • 树中节点总数在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

这题呢其实也比较简单,但是有几个比较坑的点需要在这里说一下,以防各位入坑~

先看代码:

class Solution {
public:vector<vector<int>> res;vector<int> temp;void getAllRoute(TreeNode* root, int targetSum, int sum) {if (root == nullptr)//这里一定要先判断,不然sum += root->val会报错return;
//下面两行代码一定要放到if判断的前面,不然部分样例会报错,为什么这么写各位应该是清楚地~sum += root->val;temp.push_back(root->val);if (root->left == nullptr && root->right == nullptr &&sum == targetSum) {//判断是否到了叶子结点并且当前值是否等于目标值res.push_back(temp);}getAllRoute(root->left, targetSum, sum);getAllRoute(root->right, targetSum, sum);temp.pop_back();sum -= root->val;}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {int sum = 0;if (root == nullptr)return res;getAllRoute(root, targetSum, sum);return res;}
};

看完代码,如果你觉得恍然大悟,那恭喜你,算是对回溯和深搜学的比较好的,但是如果看完代码觉得还是很懵的建议再去看看回溯,理解其中的含义再做几道题就明白了;深搜这里其实主要就是为了遍历整棵树,这个没啥可说的,不理解的评论区评论或者私信哦~

http://www.lryc.cn/news/474493.html

相关文章:

  • C02S04-Ubuntu基本使用
  • C语言 | Leetcode C语言题解之第525题连续数组
  • Qml-Transition的使用
  • Notepad++检索包含多个关键字的行
  • C语言:水仙花树,要求三位以上的N位整数每位的N次方等于数本身,全部输出出来
  • 金融贷款口子超市V2源码 Thinkphp开发的贷款和超市平台源码(亲测源码含安装视频教程)
  • redis的三种客户端
  • 边缘计算【智能+安全检测】系列教程--agx orin解决RTC时间问题
  • 数据库动态扩容:Java实现与技术策略
  • Golang | Leetcode Golang题解之第525题连续数组
  • 低代码架构浅析
  • mysql字段是datetime如何按照小时来统计
  • nacos快速启动
  • @Excel若依导出异常/解决BusinessBaseEntity里面的字段不支持导出
  • 虚拟机 Email 恢复专用工具:Virtual Machine Email Recovery
  • 代理人工智能如何应对现代威胁的速度和数量
  • element-plus版本过老,自写选项弹框增删功能
  • Python毕业设计选题:基于django+vue的宠物寄养平台的设计与实现
  • 计算机后台服务-更新下载,重启————未来之窗行业应用跨平台架构
  • springcloud通过MDC实现分布式链路追踪
  • logback日志级别动态切换四种方案
  • AI视频管理平台中使用目标检测模型中的NMS参数原理及设置原则
  • 从零开始点亮一个LED灯 —— keil下载、新建工程、版本烧录、面包板使用、实例代码
  • [pdf,epub]105页《分析模式》漫谈合集01
  • 计算机网络5层模型
  • Python毕业设计选题:基于Python的无人超市管理系统-flask+vue
  • WindowsDocker安装到D盘,C盘太占用空间了。
  • Java面试经典 150 题.P80. 删除有序数组中的重复项 II(004)
  • 【Three.js】SpriteMaterial 加载图片泛白,和原图片不一致
  • 了解神经网络中的激活函数