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

【leetcode题解C++】257.二叉树的所有路径 and 404.左叶子之和 and 112.路径总和

257. 二叉树的所有路径

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。

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

示例 1:

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]

示例 2:

输入:root = [1]
输出:["1"]

思路:递归,结束条件是一个结点没有左孩子和右孩子。题目提示中写到至少会有一个根节点,那么不用判断树空的情况。

代码实现:

class Solution {void generate(TreeNode *node, string path, vector<string> &result) {path += to_string(node->val);if(node->left && !node->left->left && !node->left->right) {result.push_back(path);return;}if(node->left) generate(node->left, path + "->", result);if(node->right) generate(node->right, path + "->", result);}    vector<string> binaryTreePaths(TreeNode* root) {string path = "";vector<string> result;//if(!root) return result;generate(root, path, result);return result;}
};

404. 左叶子之和

给定二叉树的根节点 root ,返回所有左叶子之和。

示例 1:

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

示例 2:

输入: root = [1]
输出: 0

思路:递归,迭代都可以。迭代的话,前中后续都可行,下面的代码是后序遍历,注意判断左叶子结点即可。递归的判定条件也是相同的。

代码实现1:迭代

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {stack<TreeNode *> stk;if(!root) return 0;stk.push(root);int ret = 0;TreeNode *node;while(!stk.empty()) {node = stk.top();stk.pop();if(node->left && !node->left->left && !node->left->right) ret += node->left->val;if(node->left) stk.push(node->left);if(node->right) stk.push(node->right);}return ret;}
};

代码实现2:递归

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(!root) return 0;int leftValue = 0;if(root->left && !root->left->left && !root->left->right) {leftValue = root->left->val;}return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);}
};

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

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

示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。

示例 2:

输入:root = [1,2,3], targetSum = 5
输出:false
解释:树中存在两条根节点到叶子节点的路径:
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3:

输入:root = [], targetSum = 0
输出:false
解释:由于树是空的,所以不存在根节点到叶子节点的路径。

思路:递归+回溯,当得到的结果不满足时,需要往回退一步,寻找新的可能满足需求的路径。

代码实现:

class Solution {
public:bool calculate(TreeNode *node, int count) {if(!node->left && !node->right && count == 0) return true;if(!node->left && !node->right) return false;if(node->left) {count -= node->left->val;if(calculate(node->left, count)) return true;count += node->left->val;}if(node->right) {count -= node->right->val;if(calculate(node->right, count)) return true;count += node->right->val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(!root) return false;return calculate(root, targetSum - root->val);}
};

相关文章:

【leetcode题解C++】257.二叉树的所有路径 and 404.左叶子之和 and 112.路径总和

257. 二叉树的所有路径 给你一个二叉树的根节点 root &#xff0c;按 任意顺序 &#xff0c;返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。 示例 1&#xff1a; 输入&#xff1a;root [1,2,3,null,5] 输出&#xff1a;["1->2->5",&…...

Linux——文本编辑器Vim

Linux中的所有内容以文件形式管理&#xff0c;在命令行下更改文件内容&#xff0c;常常会用到文本编辑器。我们首选的文本编辑器是Vim&#xff0c;它是一个基于文本界面的编辑工具&#xff0c;使用简单且功能强大&#xff0c;更重要的是&#xff0c;Vim是所有Linux发行版本的默…...

以“美”为鉴,探寻香港比特币现货ETF的未来发展

出品&#xff5c;欧科云链研究院 作者&#xff5c;Hedy Bi 根据The Block于1月29日的报道&#xff0c;嘉实国际成为了首家向香港证监会提交比特币现货ETF申请的机构。早在去年12月22日&#xff0c;香港证监会发布了《有关证监会认可基金投资虚拟资产的通函》&#xff0c;明确…...

Unity项目打包的方法(之一)

在 Unity 中&#xff0c;将项目打包成 .unitypackage 文件和直接压缩 Assets、Packages 和 ProjectSettings 目录有几个关键区别&#xff0c;主要体现在打包方式、使用目的和包含的内容上。 打包成 UnityPackage .unitypackage 是 Unity 的一种打包格式&#xff0c;它允许你将项…...

如何安装MySQL

如何安装MySQL 前提条件下载MySQL在 Windows 上安装 MySQL验证 MySQL 安装 MySQL是当今工业界广泛使用的最流行的关系数据库管理软件之一。它通过各种存储引擎提供多用户访问支持。它得到了甲骨文公司的支持。在本节中&#xff0c;我们将学习如何为初学者下载和安装 MySQL。 前…...

如何编写.gitignore文件

文章目录 前端架构师教你如何编写.gitignore文件.gitignore文件简介.gitignore文件的语法规则.gitignore文件的最佳实践常见问题与解决 前端架构师教你如何编写.gitignore文件 .gitignore文件简介 .gitignore文件是Git版本控制系统中一个非常有用的工具。它可以指定一组文件或…...

U-Boot学习(7):内核启动之bootz启动zImage源码分析

在上一节中&#xff0c;我们分析了U-BOOT初始化的流程&#xff0c;最后就是进入U-Boot的命令行中执行了&#xff0c;如果用户没有任何操作&#xff0c;则经过固定延时后将执行默认的bootcmd环境变量里的指令&#xff0c;那这里面肯定就是启动内核了。在U-BOOT简介及命令行指令详…...

[GN] DP学习笔记板子

文章目录 Bitset滚动数组多重背包区间DP树形dp状压dp模拟退火 Bitset 使用bitset需要引用<bitset>头文件。 其声明方法为: std::bitset<N>s; (N为s长度)常用函数&#xff1a; b.any() 判断b中是否存在值为1的二进制位 b.none() 判断b中是否不存在值为1的二…...

GLog开源库使用

Glog地址&#xff1a;https://github.com/google/glog 官方文档&#xff1a;http://google-glog.googlecode.com/svn/trunk/doc/glog.html 1.利用CMake进行编译&#xff0c;生成VS解决方案 &#xff08;1&#xff09;在glog-master文件夹内新建一个build文件夹&#xff0c;用…...

微信小程序如何实现点击上传图片功能

如下所示,实际需求中常常存在需要点击上传图片的功能,上传前显示边框表面图片显示大小,上传后将图形缩放到边框大小。 实现如下: .wxml <view class="{{img_src==?blank-area:}}" style="width:100%;height:40%;display:flex;align-items: center;jus…...

Windows Qt C++ VTK 绘制三维曲线

Qt 自带数据可视化从文档上看&#xff0c;只能实现三维曲面。 QwtPlot3D在Qt6.6.0上没编译通过。 QCustomPlot 只能搞二维。 VTK~搞起。抄官网demo。 后续需求&#xff1a; 1、对数轴 2、Y轴逆序 3、Z轴值给色带&#xff0c;类似等高线图的色带 期待各位大佬多多指导。…...

Android T 远程动画显示流程(更新中)

序 本地动画和远程动画区别是什么? 本地动画&#xff1a;自给自足。对自身SurfaceControl矢量动画进行控制。 远程动画&#xff1a;拿来吧你&#xff01;一个app A对另一个app B通过binder跨进程通信&#xff0c;控制app B的SurfaceControl矢量动画。 无论是本地动画还是远程…...

【计算机网络】【练习题及解答】【新加坡南洋理工大学】【Computer Control Network】

说明&#xff1a; 仅供学习使用。 一、题目描述 题目共4问&#xff0c;描述网络通信中的 帧传输时延&#xff08;Frame Delay&#xff09;、传播时延&#xff08;Propagation Delay&#xff09;&#xff0c;以及 链接利用率&#xff08;Link Utilization&#xff09; 的相关…...

云计算HCIE备考经验分享

大家好&#xff0c;我是来自深圳信息职业技术学院22级鲲鹏3-1班的刘同学&#xff0c;在2023年9月19日成功通过了华为云计算HCIE认证&#xff0c;并且取得了A的成绩。下面把我的考证经验分享给大家。 转专业进鲲鹏班考HCIE 大一上学期的时候&#xff0c;在上Linux课程的时候&…...

Threejs API——`OrbitControls`相机控件

文章目录 API用法API OrbitControls 相机控制用法 导入import {OrbitControls } from three/examples/jsm/controls/OrbitControls.js import {DRACOLoader,AmbientLight,Color,MOUSE,...

远程教育:低代码在教育技术领域的重塑之力

新冠肺炎大流行对世界各地的行业产生了影响&#xff0c;其中一些行业的影响远远超过其他行业。食品、零售、供应链、娱乐和航空业是受影响最大的行业&#xff0c;为确保不间断运营&#xff0c;这引发了一场数字革命。相信&#xff0c;这种数字化的采用将长期保持下去&#xff0…...

vue 模板语法值class操作

class.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>class</title><!-- 确保引入正确的Vue版本库&#xff0c;下面只是示例&#xff0c;需要替换为实际可工作的CDN地址 --><sc…...

MySQL的原生API实现插入数据后在可视化工具上不显示的问题解决

显示表中有两行数据&#xff0c;该表也设置了主键和唯一索引 点进表里看却没有数据 问题原因出现在这里&#xff0c;虽然很多常用的数据库连接池都会开启自动提交&#xff0c;但ibatis的SqlSession使用sessionFactory.openSession()创建时&#xff0c;默认的自动提交是false&am…...

Blender教程(基础)-内插面、分离、环切、倒角-08

一、内插面 菜单位置如下图位置。 单击需要处理的面&#xff0c;出现一个黄色的圈。 1、菜单选中内插 鼠标悬停在黄色圈内单击左键可以来回实现内插&#xff0c;但是发现并不好操作。 2、快捷键内插 在选中需要操作的面之后&#xff0c;鼠标移动到外面&#xff0c;键盘在英…...

Unity 自动轮播、滑动轮播

如图所示&#xff0c;可设置轮播间隔&#xff0c;可左右滑动进行轮播 1.在UGUI创建个Image&#xff0c;添加自动水平组件 2.添加并配置脚本 3.代码如下&#xff0c;都有注释 using UnityEngine; using UnityEngine.UI;public class IndicatorManager : MonoBehaviour {public …...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...