剑指offer面试题34:在二叉树中和为某一值的路径

news/2024/5/30 18:38:38/文章来源:https://blog.csdn.net/weixin_44269804/article/details/136645239

面试题34:在二叉树中和为某一值的路径

题目:

LCR 153. 二叉树中和为目标值的路径 - 力扣(LeetCode)

给你二叉树的根节点 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
输出:[]

思路:

就是用深度优先遍历,直接将路径上的值存在一个vector容器中,然后当到达了叶子结点就判断容器中的值是否满足target,满足就加入最终的容器中,然后注意这里要对加入的值进行一个删除,达到回溯的目的。

代码:

/*** 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:vector<vector<int>> res;vector<int> ans;void dfs(TreeNode* root, int target){if(root==nullptr) return ;ans.push_back(root->val);if(root->left==nullptr&&root->right==nullptr){int sum=0;for(auto item:ans)sum+=item;if(sum==target)res.push_back(ans);}else{dfs(root->left,target);dfs(root->right,target);}ans.pop_back();}vector<vector<int>> pathTarget(TreeNode* root, int target) {dfs(root,target);return res;}
};

考点:

  1. 二叉树的深度优先遍历
  2. 回溯问题

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

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

相关文章

格子表单GRID-FORM | 必填项检验 BUG 修复实录

格子表单/GRID-FORM已在Github 开源&#xff0c;如能帮到您麻烦给个星&#x1f91d; GRID-FORM 系列文章 基于 VUE3 可视化低代码表单设计器嵌套表单与自定义脚本交互文档网站搭建&#xff08;VitePress&#xff09;与部署&#xff08;Github Pages&#xff09;必填项检验 BUG…

新版Android Studio火烈鸟 在新建项目工程时 无法选java的语言模板解决方法

前言 最近下载最新版androidstudio时 发现不能勾选java语言模板了 如果快速点击下一步 新建项目 默认是kotlin语言模板 这可能和google主推kt语言有关 勾选1 如图所示 如果勾选 No Activity 这个模板 是可以选java语言模板的 但是里面没有默认的Activity 勾选2 和以前的用法…

CubeMX使用教程(5)——定时器PWM输出

本篇我们将利用CubeMX产生频率固定、占空比可调的两路PWM信号输出 例如PA6引脚输出100Hz的PWM&#xff1b;PA7引脚输出500Hz的PWM&#xff0c;双路同时输出 我们还是利用上一章定时器中断的工程进行学习&#xff0c;这样比较方便 首先打开CubeMX对PA6、PA7进行GPIO配置 注&a…

spring 面试题

1.springboot自动装配 从 这个META-INF/spring-autoconfigure-metadata.properties加载文件 2.springbean 的生命周期 3.spring 如何解绝循环依赖 private final Map<String, Object> earlySingletonObjects new ConcurrentHashMap<>(16); private final Map&l…

【ArcGIS】栅格数据进行标准化(归一化)处理

栅格数据进行标准化&#xff08;归一化&#xff09;处理 方法1&#xff1a;栅格计算器方法2&#xff1a;模糊分析参考 栅格数据进行标准化(归一化)处理 方法1&#xff1a;栅格计算器 栅格计算器&#xff08;Raster Calculator&#xff09; 计算完毕后&#xff0c;得到归一化…

【Python使用】python高级进阶知识md总结第2篇:HTTP 请求报文,HTTP响应报文【附代码文档】

python高级进阶全知识知识笔记总结完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;操作系统&#xff0c;虚拟机软件&#xff0c;Ubuntu操作系统&#xff0c;Linux内核及发行版&#xff0c;查看目录命令&#xff0c;切换目录命令&#xff0c;绝对路径和相对…

Python环境搭建 -- Python与PyCharm安装

一、Python安装 我们先找到Python的官方网站&#xff0c;在浏览器中搜索Python即可&#xff0c;然后进入Python官网 点击Downloads&#xff0c;选择对应匹配的操作系统 点进去之后&#xff0c;Python的版本分为稳定的版本和前置版本&#xff0c;前置的版本就是还没有发行的版本…

【深入理解设计模式】模板方法模式

模板方法模式 模板方法模式是一种行为设计模式,它定义了一个操作中的算法骨架,将某些步骤延迟到子类中实现。模板方法模式使得子类可以不改变算法结构的情况下,重新定义算法的某些特定步骤。 概述 在面向对象程序设计过程中&#xff0c;程序员常常会遇到这种情况&#xff1a;…

在【IntelliJ IDEA】中配置【Tomcat】【2023版】【中文】【图文详解】

作为一款功能强大的集成开发环境&#xff08;IDE&#xff09;&#xff0c;IntelliJ IDEA为Web服务器提供了卓越的支持&#xff0c;从而极大地简化了程序员在Web开发过程中的工作流程。学习Java Web开发实质上就是掌握如何创造动态Web资源&#xff0c;这些资源在完成开发后&…

python之格式化输出format()函数使用总结

在 Python 中&#xff0c;format 方法是一种用于字符串格式化的强大工具。它允许你将变量或表达式插入到字符串中&#xff0c;并根据需要进行格式化。下面是对 format 方法的详细介绍&#xff1a; format 方法的基本语法如下&#xff1a; formatted_string "string {0} …

静态路由--添加路由表,实现非直连网段的通信

建立拓扑&#xff1a; 路由器**只有直连网段的路由表,而对非直连并不拥有,因此要在路由器的路由表中手动添加非直连网段的路由. ** 也就是说对于AR2来说&#xff0c;**网段192.168.10.0**和**网段192.168.40.0**是他的直连网段。进一步说这两个网端的设备可以相互通信而网段19…

Linux网络套接字之TCP网络程序

(&#xff61;&#xff65;∀&#xff65;)&#xff89;&#xff9e;嗨&#xff01;你好这里是ky233的主页&#xff1a;这里是ky233的主页&#xff0c;欢迎光临~https://blog.csdn.net/ky233?typeblog 点个关注不迷路⌯▾⌯ 目录 一、接口介绍 1.socket 2.listen 3.accept…

ssm蛋糕甜品商城系统(程序+文档+数据库)

** &#x1f345;点赞收藏关注 → 私信领取本源代码、数据库&#x1f345; 本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目&#xff0c;希望你能有所收获&#xff0c;少走一些弯路。&#x1f345;关注我不迷路&#x1f345;** 一、研究背景…

C# MES通信从入门到精通(1)——串口传输文件

前言: 在上位机软件开发领域,有一些工厂的mes系统需要我们通过串口发送文件的方式把一些图片或者检测数据csv文件等发送给服务器,这种方式是一些比较旧的工厂采用的方式,但是这种方式也是存在的,本文就是讲解如何使用串口发送文件详情见下文。 1、串口发送文件思路 将需…

Haproxy 负载均衡集群

一. Haproxy 1. Haproxy 介绍 HAProxy 是法国开发者威利塔罗 (Willy Tarreau) 在2000年使用C语言开发的一个开源软件&#xff0c;是一款具备高并发(一万以上)、高性能的TCP和HTTP负载均衡器&#xff0c;支持基于cookie的持久性&#xff0c;自动故障切换&#xff0c;支持正则…

脚手架cli快速创建Vue2/Vue3项目

前言&#xff1a; 本文的nodejs版本是14.21.3 第一步 进入cmd窗口 1、全局安装webpack npm install webpack-g&#xff0c; npm install webpack-g 第二步 2、全局安装vue脚手架 npm install -g vue/cli 第三步 3、初始化vue项目 &#xff08;vue脚手架使用webpack模…

全排列+力扣

题目 题目链接 . - 力扣&#xff08;LeetCode&#xff09; 题目描述 代码实现 class Solution {vector<vector<int>> ret;vector<int> path;bool used[7]; public:vector<vector<int>> permute(vector<int>& nums) {_permute(nums…

CSA发布|《面向IAM的零信任原则与指南》

关注国际云安全联盟公众号&#xff0c;回复关键词 “零信任”即可获取报告完整版。 零信任框架近年在国内发展趋于成熟&#xff0c;落地案例也越来越多&#xff0c;在抵御诸如网络钓鱼的常见、勒索病毒等攻击中起到了重要作用&#xff0c;其中身份和验证、决策和授权是零信任框…

阿里云第一次面试记录

java多态&#xff1f; 多态表示一个对象具有多种的状态&#xff0c;具体表现为父类的引用指向子类的实例 Fu f Zi z(); 多态是同一个行为具有多个不同表现形式或形态的能力。 多态就是同一个接口&#xff0c;使用不同的实例而执行不同操作 特点&#xff1a; 对象类型和引用类型…

手机和电脑同步的好用记事本软件有哪些

我常常需要随手记录各种信息&#xff0c;以便随时查阅和使用。比如&#xff0c;在下班路上&#xff0c;我会用手机记录明天要处理的工作事项、购物清单&#xff0c;或是某个突然迸发的创意想法&#xff1b;而在办公室&#xff0c;我则需要在电脑上整理会议纪要、项目计划&#…