【递归】7. leetcode 404 左叶子之和
1 题目描述
题目链接:左叶子之和
2 解答思路
递归分为三步,接下来就按照这三步来思考问题
第一步:挖掘出相同的子问题 (关系到具体函数头的设计)
第二步:只关心具体子问题做了什么 (关系到具体函数体怎么写,是一个宏观的过程)
第三步:找到递归的出口,防止死递归 (关系到如何跳出递归)
2.1 相同的子问题(函数头设计)
相同的子问题:寻找二叉树的左叶子,就是寻找二叉树的左子树的左叶子和右子树的左叶子。
根据相同的子问题,思考具体的方法:将所有的左叶子放入到一个vector中,最后使用循环将值相加到一起。
下面是leetcode给的接口:
int sumOfLeftLeaves(TreeNode* root) {}
传入一个TreeNode*
类型的参数,返回是左叶子的和,int
类型。
根据之前的分析,我们的参数是一个TreeNode*
类型,还有一个vector< int>
类型。因为值存储在vector
中,最终计算,所以返回值类型为void
。最终函数头的设计如下:
void sum(TreeNode* root, vector<int>& res){}
2.2 具体的子问题做了什么(函数体的实现)
具体子问题做了什么:
1.首先判断该节点的左孩子是不是叶子节点
,如果是,则加入到vector中。
2.在当前节点的左子树中寻找
3.在当前节点的右子树中寻找
递归的出口:当前节点为空。
最终函数体的书写:
void sum(TreeNode* root, vector<int>& res){if (root == nullptr)return;//如果当前节点有左孩子 并且 左孩子为叶子节点if ((root->left) && ((root->left->left == nullptr) && (root->left->right == nullptr)))res.push_back(root->left->val); //将左孩子的值加入到vector中//递归左子树sum(root->left, res);//递归右子树sum(root->right, res);}
3 总结
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {vector<int> res;sum(root, res);int s = 0;for (int i = 0; i < res.size(); ++ i){s += res[i];}return s;}//只要叶子节点void sum(TreeNode* root, vector<int>& res){if (root == nullptr)return;//如果当前节点有左孩子 并且 左孩子为叶子节点if ((root->left) && ((root->left->left == nullptr) && (root->left->right == nullptr)))res.push_back(root->left->val); //将左孩子的值加入到vector中//递归左子树sum(root->left, res);//递归右子树sum(root->right, res);}
};
1. 相同的子问题:寻找二叉树的左叶子,就是寻找二叉树的左子树的左叶子和右子树的左叶子。
2. 具体子问题做了什么:首先判断该节点的左孩子是不是叶子节点,如果是,则加入到vector中。在当前节点的左子树中寻找。在当前节点的右子树中寻找。
3. 递归的出口:当前节点为空。
相关文章:

【递归】7. leetcode 404 左叶子之和
1 题目描述 题目链接:左叶子之和 2 解答思路 递归分为三步,接下来就按照这三步来思考问题 第一步:挖掘出相同的子问题 (关系到具体函数头的设计) 第二步:只关心具体子问题做了什么 (关系…...

react+antdMobie实现消息通知页面样式
一、实现效果 二、代码 import React, { useEffect, useState } from react; import style from ./style/index.less; import { CapsuleTabs, Ellipsis, Empty, SearchBar, Tag } from antd-mobile; //消息通知页面 export default function Notification(props) {const [opti…...

Git 撤销一个已经push到远端仓库的commit
在 Git 中,撤销一个已经推送到远程仓库的改动有几种不同的方法,具体取决于你是否想要完全删除改动,还是只是恢复文件的某个状态。以下是常见的几种方法: git revert 撤销特定的commit git revert 是最安全的方法,因为…...

lambda表达式底层实现
一、lambda 代码 & 反编译 原始Java代码 假设我们有以下简单的Java程序,它使用Lambda表达式来遍历并打印一个字符串列表: import java.util.Arrays; import java.util.List;public class LambdaExample {public static void main(String[] args) {…...

鸿蒙NEXT开发-组件事件监听和状态管理(基于最新api12稳定版)
注意:博主有个鸿蒙专栏,里面从上到下有关于鸿蒙next的教学文档,大家感兴趣可以学习下 如果大家觉得博主文章写的好的话,可以点下关注,博主会一直更新鸿蒙next相关知识 专栏地址: https://blog.csdn.net/qq_56760790/…...

《More Effective C++》的学习
引用与指针 没有所谓的null reference reference一定需要代表某个对象,所以C要求reference必须有初值。 QString &s; 使用reference可能比使用pointer更高效。 因为reference一定是有效的,而指针可能为空(需要多加一个判断࿰…...

Leetcode面试经典150题-322.零钱兑换
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。 示…...

python17_len()函数
len()函数 A B "" C "hello world" D 18 E 18def len_test(s):try:# 尝试计算字符串的长度length len(s)return lengthexcept TypeError:# 如果不是字符串,则返回 None 或者提示错误return Noneif __name__ "__main__":# 单…...

车视界系统小程序的设计
管理员账户功能包括:系统首页,个人中心,汽车品牌管理,汽车颜色管理,用户管理,汽车信息管理,汽车订单管理系统管理 微信端账号功能包括:系统首页,汽车信息,我…...
SQLCMD命令行工具导入数据并生成对应的日志文件
SQLCMD是一个命令行工具,专门用于在Microsoft SQL Server数据库上运行SQL脚本和管理任务。它提供了一种交互式和自动化的方式来执行SQL命令和脚本,并允许用户与SQL Server数据库进行高效的交互。以下是关于SQLCMD的详细介绍: 主要功能 执行SQL脚本: SQLCMD可以执行包含SQL…...

tauri中加载本地文件图片或者下载网络文件图片后存储到本地,然后通过前端页面展示
有一个需求是需要将本地上传的文件或者网络下载的文件存储到本地,并展示在前端页面上的。其实如果只是加载本地文件,然后展示还是挺简单的,可以看我的文章:tauri程序加载本地图片或者文件在前端页面展示-CSDN博客 要想实现上述需…...

QSqlDatabase在多线程中的使用
Qt中多线程使用数据库_qt数据库管理类支持多数据库,多线程-CSDN博客 1. 代码: #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QPushButton> #include <QSqlDatabase> #include <QSqlQuery> #include <QSqlError>…...

【无人机设计与控制】Multi-UAV|多无人机多场景路径规划算法MATLAB
摘要 本研究探讨了多无人机路径规划问题,提出了三种不同算法的对比分析,包括粒子群优化(PSO)、灰狼优化(GWO)和鲸鱼优化算法(WOA)。利用MATLAB实现了多场景仿真实验,验证…...

Visual Studio C# 编写加密火星坐标转换
Visual Studio C# 编写加密火星坐标转换 1、WGS84坐标转GCJ02火星坐标2、GCJ02火星坐标转WGS84坐标(回归计算)3、GCJ02火星坐标转BD09百度坐标4、BD09百度坐标转GCJ02火星坐标(回归计算)5、坐标公共转换类6、地图显示7、程序简单界…...

微服务-流量染色
1. 功能目的 通过设置请求头的方式将http请求优先打到指定的服务上,为微服务开发调试工作提供便利 请求报文难模拟:可以直接在测试环境页面上操作,流量直接打到本地IDEA进行debug请求链路较长:本地开发无需启动所有服务…...
C语言实现 操作系统 经典的进程同步问题(2)
哲学家进餐问题 哲学家进餐问题是一个经典的同步问题,涉及多个哲学家试图同时用餐,但每个哲学家左右两边只有一把叉子。为了避免死锁和饥饿,可以使用记录型信号量(也称为计数信号量)来管理叉子的使用。 1、利用记录型…...

有效的字母异位词【字符串哈希】
题目 题解: 1.排序: #include<algorithm>class Solution{public:bool isAnagram(string s,string t){sort(s.begin(),s.end());sort(t.begin(),t.end());return st;} } 时间复杂度O(nlogn) 2.哈希表 #include<algorithm>int hash1[100]; …...
如何选择与运用工具提升工作效率的秘密指南
一、引言 ---- 在当今这个信息爆炸的时代,编程工具的选择对于开发者的工作效率至关重要。从智能的代码编辑器到强大的版本控制工具,再到那些能让我们事半功倍的自动化脚本,每一款工具都有其独特的优势和价值。那么,哪款编程工具…...

Spring系列 AOP实现过程
文章目录 实现原理EnableAspectJAutoProxyAnnotationAwareAspectJAutoProxyCreator 代理创建过程wrapIfNecessarygetAdvicesAndAdvisorsForBeanfindCandidateAdvisorsfindAdvisorsThatCanApply createProxy AspectJ注解处理代理调用过程 实现原理 本文源码基于spring-aop-5.3.…...

C语言 getchar 函数完全解析:掌握字符输入的关键
前言 在C语言中,getchar 是一个非常实用的函数,用于从标准输入流(通常是键盘)读取单个字符。这对于处理文本输入非常有用,尤其是在需要逐个字符处理的情况下。本文将深入探讨 getchar 函数的用法和特点,并…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...

面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...

【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...