【递归】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 函数的用法和特点,并…...

华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...

Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...