Leetcode刷题详解——求根节点到叶节点数字之和
1. 题目链接:129. 求根节点到叶节点数字之和
2. 题目描述:
给你一个二叉树的根节点
root,树中每个节点都存放有一个0到9之间的数字。每条从根节点到叶节点的路径都代表一个数字:
- 例如,从根节点到叶节点的路径
1 -> 2 -> 3表示数字123。计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1:
输入:root = [1,2,3] 输出:25 解释: 从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此,数字总和 = 12 + 13 = 25示例 2:
输入:root = [4,9,0,5,1] 输出:1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495 从根到叶子节点路径 4->9->1 代表数字 491 从根到叶子节点路径 4->0 代表数字 40 因此,数字总和 = 495 + 491 + 40 = 1026提示:
- 树中节点的数目在范围
[1, 1000]内0 <= Node.val <= 9- 树的深度不超过
10
3. 解法(前序遍历)
前序遍历的顺序为根结点->左子树->右子树
3.1 算法思路:
在前序遍历的过程中,我们可以往左右子树传递信息,并且在回溯时得到左右子树的返回值。递归函数可以帮助我们完成两件事情:
- 将父节点的数字与当前节点的信息整合到一起,计算出当前节点的数字,然后传递到下一层进行递归
- 当遇到叶子节点的时候,就不再向下传递信息,而是将整合的结果向上一种回溯到根节点
在递归结束时,根节点需要返回的值也就被更新为了整棵树的数字之和
3.2 算法流程:
递归函数设计:int dfs(TreeNode* root,int num)
- 返回值:当前子树计算的结果(数字和)
- 参数num:递归过程中往下传递的信息(父节点的数字)
- 函数作用:整合父节点的信息与当前节点的信息计算当前节点数字,并向下传递,在回溯时返回当前子树(当前节点作为子树根节点)数字和。
递归函数流程:
- 当遇到空节点的时候,说明这条路从根节点开始没有分支,返回
0 - 结合父节点传下的信息以及当前节点的
val,计算出当前节点数字num - 如果当前节点是叶子节点,直接返回整合后的结果
num - 如果当前节点不是叶子节点,将
num传到左右子树中去,得到左右子树节点路径的数字和,然后相加后返回结果

3.3 C++算法代码:
/*** 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:int sumNumbers(TreeNode* root) {return dfs(root,0);}int dfs(TreeNode*root,int num){num=num*10+root->val;//如果左右子树为空,说明是没有左右子树,返回numif(root->left==nullptr&&root->right==nullptr)return num;int ret=0;if(root->left)ret+=dfs(root->left,num);if(root->right)ret+=dfs(root->right,num);return ret;}
};
相关文章:
Leetcode刷题详解——求根节点到叶节点数字之和
1. 题目链接:129. 求根节点到叶节点数字之和 2. 题目描述: 给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字: 例如,从根节点到叶节点的路径 1…...
emq集群配置nginx做负载均衡
emq集群配置nginx做负载均衡 创建 EMQ X 节点集群 emqx 集群搭建 例如: 节点IP 地址emqx192.168.1.17192.168.1.17emqx192.168.1.18192.168.1.18emqx192.168.1.19192.168.1.19 配置 /etc/nginx/nginx.conf mqtt集群搭建并使用nginx做负载均衡_亲测得结论 示例: vim /et…...
【JAVA学习笔记】60 - 坦克大战1.0-绘图坐标体系、事件处理机制
项目代码 https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter16/src/com/yinhai 绘图坐标体系 一、基本介绍 下图说明了Java坐标系。坐标原点位于左上角,以像素为单位。在Java坐标系中,第一个是x坐标,表示当前位置为…...
Android13 安装谷歌GMS导致打开蓝牙失败解决方法
Android13 安装谷歌GMS导致打开蓝牙失败解决方法 文章目录 Android13 安装谷歌GMS导致打开蓝牙失败解决方法一、前言二、解决方法1、简单的解决方法2、添加属性和日志解决 三、分析1、查看异常日志2、 查看蓝牙相关日志 四、总结1、Android13 安装谷歌GMS导致打开蓝牙失败具体原…...
独创改进 | RT-DETR 引入双向级联特征融合结构 RepBi-PAN | 附手绘结构图原图
本专栏内容均为博主独家全网首发,未经授权,任何形式的复制、转载、洗稿或传播行为均属违法侵权行为,一经发现将采取法律手段维护合法权益。我们对所有未经授权传播行为保留追究责任的权利。请尊重原创,支持创作者的努力,共同维护网络知识产权。 文章目录 YOLOv6贡献RepBi-…...
Ubuntu下安装vscode,并解决终端打不开vscode的问题
Visual Studio Code安装 1,使用 apt 安装 Visual Studio Code 在官方的微软 Apt 源仓库中可用。按照下面的步骤进行即可: 以 sudo 用户身份运行下面的命令,更新软件包索引,并且安装依赖软件: sudo apt update sud…...
Spring Boot Actuator 漏洞利用
文章目录 前言敏感信息泄露env 泄露配置信息trace 泄露用户请求信息mappings 泄露路由信息heapdump泄露堆栈信息 前言 spring对应两个版本,分别是Spring Boot 2.x和Spring Boot 1.x,因此后面漏洞利用的payload也会有所不同 敏感信息泄露 env 泄露配置信…...
acwing算法基础之数据结构--trie算法
目录 1 基础知识2 模板3 工程化 1 基础知识 trie树算法,也叫作字典树算法。 用处:用来高效存储和查找字符串集合的数据结构。 (一) 定义变量。 const int N 1e5 10; int son[N][26], cnt[N], idx; char str[N];(二…...
ES from+size>10000报错
参考博客 from size > 10000就会报错 Result window is too large, from size must be less than or equal to: [10000] but was [10001]. See the scroll api for a more efficient way to request large data sets. This limit can be set by changing the [index.max_…...
(04)Mycat实现分库
1、如何选择分库表 #客户表 rows:20万 CREATE TABLE customer(id INT AUTO_INCREMENT,NAME VARCHAR(200),PRIMARY KEY(id) );#订单表 rows:600万 CREATE TABLE orders(id INT AUTO_INCREMENT,order_type INT,customer_id INT,amount DECIMAL(10,2),PRIMARY KEY(id) ); #…...
DeepSORT多目标跟踪——算法流程与源码解析
一、目标检测与目标追踪 1. 目标检测 在目标检测任务中,主要目标是识别图像或视频帧中存在的物体的位置和类别信息。这意味着目标检测算法需要定位物体的边界框(Bounding Box)并确定每个边界框内的物体属于哪个类别(如人、汽车、…...
C++查漏补缺与新标准(C++20,C++17,C++11)02 C++快速回顾(二)
本内容参考C20高级编程 C风格的数组 //形如 int myArray[3]{2};一个比较新颖的获取C风格数组大小的函数std::size(),返回size_t类型(在中定义的无符号整数) #include <iostream> using namespace std;int main() {int myArray[5] {…...
红米K40功能介绍
红米K40是小米旗下的一款高性能智能手机。以下是红米K40的一些功能介绍及新增功能: 1.高性能处理器:红米K40搭载了骁龙870处理器,提供强大的性能和流畅的操作体验。 2.120Hz刷新率屏幕:红米K40采用了6.67英寸的AMOLED全面屏&…...
壹[1],Opencv常用结构
1,Point类:点表示 point表示二维结构的点,(x,y) cv::Point point; point.x 100; point.y 100; 2,Scalar类:颜色表示 cv::Scalar colorBlue(255,0,0);//蓝色 cv::Scalar colorGreen(0, 255, 0);//绿色 cv::Scalar colorRed(0, …...
Linux常用指令(一)——目录操作
Linux目录操作 1.1 目录切换 cd1.2 目录查看 ls1.3 创建目录 mkdir1.4 删除目录 rm1.5 复制目录 cp1.6 删除目录 rm1.7 搜索目录 find1.8 查看当前所在目录 pwd 更加完整的Linux常用指令 1.1 目录切换 cd # 切换到根目录 cd / # 切换到根目录的usr目录 cd /usr # 返回上一级目…...
前端基础之jQuery
一.什么是jQuery jQuery是一个轻量级的、兼容多浏览器的JavaScript库。jQuery使用户能够更方便地处理HTML Document、Events、实现动画效果、方便地进行Ajax交互,能够极大地简化JavaScript编程。它的宗旨就是:“Write less, do more.“ jQuery内部封装了…...
【基于HTML5的网页设计及应用】——实现个人简历表格和伪类选择器应用
🎃个人专栏: 🐬 算法设计与分析:算法设计与分析_IT闫的博客-CSDN博客 🐳Java基础:Java基础_IT闫的博客-CSDN博客 🐋c语言:c语言_IT闫的博客-CSDN博客 🐟MySQL:…...
思考(九十二):DBProxy实现多级存储和事务处理
DBProxy 数据处理的主控室 后端开发一块重要的内容就是如何处理数据。比如: 问题说明统一的访问界面如游戏服只需要 Load、Save、Begin、Commit、Rollback 接口多级存储来降低成本如热数据在 Redis ;冷数据在 MySQL ;长时间非活跃,则归档 OSS同个逻辑涉及多个数据更新要么…...
新手入门Python一定要看的八个超实用建议!
文章目录 前言一、项目文件事先做好归档二、永远不要手动修改源数据并且做好备份三、做好路径的正确配置四、代码必要的地方做好备注与说明五、加速你的Python循环代码六、可视化你的循环代码进度七、使用高效的异常捕获工具八、要多考虑代码健壮性关于Python技术储备一、Pytho…...
Centos 7.x上利用certbot申请Let‘s Encrypt的SSH证书(HTTPS证书)
目录 01-安装Certbot02-在网站的根目录依次新建文件夹.well-known和acme-challenge03-申请证书 要在CentOS 7.x上为域名申请Let’s Encrypt证书,你可以使用Certbot工具,它是一个自动化证书颁发工具,用于管理Let’s Encrypt证书。以下是在Cent…...
终极文档处理方案:AnythingLLM如何实现PDF/TXT/DOCX全格式智能解析
终极文档处理方案:AnythingLLM如何实现PDF/TXT/DOCX全格式智能解析 【免费下载链接】anything-llm 这是一个全栈应用程序,可以将任何文档、资源(如网址链接、音频、视频)或内容片段转换为上下文,以便任何大语言模型&am…...
华为MatePad 11鸿蒙2.0平板变身编程本:保姆级AidLux+VSCode配置避坑指南
华为MatePad 11鸿蒙平板编程环境搭建实战:AidLux与VSCode高效配置指南 在移动办公与碎片化学习成为主流的今天,将华为MatePad 11这样的高性能平板转变为便携式编程工作站,正成为越来越多开发者的现实需求。鸿蒙系统2.0的分布式能力与AidLux的…...
ChatBI 开源产品实战解析:从语义层到Agent,如何选择你的AI数据助手?
1. 为什么企业需要AI数据助手? 想象一下这个场景:市场部的小王需要统计上季度各区域的销售数据,他对着Excel表格里密密麻麻的数字发愁,不得不找IT部门帮忙写SQL查询。三天后拿到数据时,业务窗口期已经错过——这是很多…...
VeighNa量化框架实战:如何免费获取TuShare金融数据(附完整接入代码)
VeighNa量化框架实战:零成本高效获取TuShare金融数据的完整指南 在量化交易领域,数据获取往往是第一个需要跨越的门槛。对于个人开发者和小型团队而言,如何在预算有限的情况下获取高质量的金融数据,成为决定项目成败的关键因素之一…...
Qwen2.5-VL-7B-Instruct实操手册:对话历史自动保存+一键清空功能详解
Qwen2.5-VL-7B-Instruct实操手册:对话历史自动保存一键清空功能详解 1. 开篇:你的全能视觉助手来了 今天给大家介绍一个特别实用的工具——基于Qwen2.5-VL-7B-Instruct多模态大模型的视觉交互工具。这个工具专门为RTX 4090显卡优化过,用上了…...
从智慧灯杆到无人驾驶:如何用Raspberry Pi 4和Arduino搭建微型智慧城市实验平台
从智慧灯杆到无人驾驶:如何用Raspberry Pi 4和Arduino搭建微型智慧城市实验平台 在创客文化和高校工程教育中,低成本硬件的创新应用正掀起一场微型智慧城市实验的革命。只需一块树莓派主板、几个传感器和开源软件,就能在桌面上复现价值数百万…...
微信聊天记录永久保存与智能分析:WeChatMsg完全使用指南
微信聊天记录永久保存与智能分析:WeChatMsg完全使用指南 【免费下载链接】WeChatMsg 提取微信聊天记录,将其导出成HTML、Word、CSV文档永久保存,对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trending/we/WeC…...
5个高效能技巧:人工智能术语库全场景应用从入门到精通
5个高效能技巧:人工智能术语库全场景应用从入门到精通 【免费下载链接】Artificial-Intelligence-Terminology-Database 这个仓库包含一个关于人工智能术语的数据库。适合AI研究者、学生以及希望了解AI专业术语的人士。特点是包含大量AI相关词汇,有助于理…...
Pixel Fashion Atelier基础教程:硬核8-Bit界面操作逻辑与非对称布局解析
Pixel Fashion Atelier基础教程:硬核8-Bit界面操作逻辑与非对称布局解析 1. 像素时装锻造坊简介 Pixel Fashion Atelier是一款基于Stable Diffusion与Anything-v5的图像生成工具,它彻底改变了传统AI工具的界面设计理念。这款工具将复古日系RPG的"…...
YOLOv7剪枝实战:5种高效剪枝方法对比与代码实现
YOLOv7剪枝实战:5种高效剪枝方法对比与代码实现 在目标检测领域,YOLOv7以其卓越的速度-精度平衡成为工业界宠儿。但当我们将模型部署到边缘设备或需要高吞吐量的生产环境时,原始模型的计算量和参数量往往成为瓶颈。这时,模型剪枝技…...


