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…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...


