LeetCode404. 左叶子之和
404. 左叶子之和
文章目录
- [404. 左叶子之和](https://leetcode.cn/problems/sum-of-left-leaves/)
- 一、题目
- 二、题解
- 方法一:递归
- 方法二:迭代
一、题目
给定二叉树的根节点 root ,返回所有左叶子之和。
示例 1:

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
示例 2:
输入: root = [1]
输出: 0
提示:
- 节点数在
[1, 1000]范围内 -1000 <= Node.val <= 1000
二、题解
方法一:递归
算法思路:
题目要求计算二叉树中所有左叶子节点的值之和。我们可以使用递归来解决这个问题。递归的思想是,对于每个节点,我们判断它是否是左叶子节点,如果是,则将其值加到结果中,然后递归地处理它的左子树和右子树。
具体实现:
-
我们首先定义一个变量
sum来保存左叶子节点值的和,并初始化为0。 -
在递归函数
sumOfLeftLeaves中,我们首先检查当前节点是否为空,如果为空,则返回0。 -
然后,我们检查当前节点的左子节点是否存在,以及左子节点是否为叶子节点。如果是叶子节点,则将其值加到
sum中。 -
最后,我们递归地处理当前节点的左子树和右子树,将它们的返回值累加到
sum中。 -
在每一层递归结束后,函数返回当前子树中左叶子节点的值之和。
/*** 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 sumOfLeftLeaves(TreeNode* root) {int sum = 0;if (root == nullptr) {return 0;}// 判断左子节点是否为叶子节点,如果是则将值加入 sumif (root->left && !root->left->left && !root->left->right) {sum += root->left->val;}// 递归处理左子树和右子树,并累加结果到 sumreturn sum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);}
};
算法分析:
-
时间复杂度:遍历整个二叉树的时间复杂度为 O(N),其中 N 是二叉树的节点数。在每个节点上,我们进行常数时间的判断和加法操作。
-
空间复杂度:递归函数的调用会占用栈空间,递归的深度最坏情况下为树的高度,所以空间复杂度为 O(H),其中 H 是二叉树的高度。在最坏情况下,二叉树可能退化为链表,高度为 N,此时空间复杂度为 O(N)。但在一般情况下,二叉树的高度平衡,空间复杂度会接近 O(logN)。
方法二:迭代
算法思路:
- 我们可以使用深度优先搜索(DFS)来遍历二叉树,使用栈来辅助遍历。
- 在遍历的过程中,对于每个节点,我们检查它的左子节点是否存在,如果存在,继续检查左子节点是否为叶子节点(即没有左右子节点)。如果是叶子节点,则将其值加到累加器
sum中。 - 对于非叶子节点,我们将左子节点压入栈,以便后续继续检查。
- 然后,无论是否有右子节点,都将右子节点压入栈,以确保我们遍历了所有可能的路径。
具体实现:
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {stack<TreeNode*> st;int sum = 0;if (root == nullptr) {return 0;}st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();if (node->left) {if (!node->left->left && !node->left->right) {sum += node->left->val; // 如果左子节点是叶子节点,将值加入 sum} else {st.push(node->left); // 如果左子节点不是叶子节点,将左子节点压入栈}}if (node->right) {st.push(node->right); // 将右子节点压入栈,无论是否为叶子节点}}return sum;}
};
算法分析:
- 时间复杂度:遍历整个二叉树的时间复杂度为 O(N),其中 N 是二叉树的节点数。在每个节点上,我们进行常数时间的判断、加法和栈操作。
- 空间复杂度:使用了一个栈来辅助遍历,栈的空间占用与二叉树的高度相关,最坏情况下为 O(N)。因此,总体空间复杂度为 O(N)。
相关文章:
LeetCode404. 左叶子之和
404. 左叶子之和 文章目录 [404. 左叶子之和](https://leetcode.cn/problems/sum-of-left-leaves/)一、题目二、题解方法一:递归方法二:迭代 一、题目 给定二叉树的根节点 root ,返回所有左叶子之和。 示例 1: 输入: root [3,9…...
Nginx 高性能内存池 ----【学习笔记】
跟着这篇文章学习: c代码实现一个高性能内存池(超详细版本)_c 内存池库_linux大本营的博客-CSDN博客https://blog.csdn.net/qq_40989769/article/details/130874660以及这个视频学习: nginx的内存池_哔哩哔哩_bilibilihttps://w…...
iOS--frame和bounds
坐标系 首先,我们来看一下iOS特有的坐标系,在iOS坐标系中以左上角为坐标原点,往右为X正方向,往下是Y正方向如下图: bounds和frame都是属于CGRect类型的结构体,系统的定义如下,包含一个CGPoint…...
docker logs 使用说明
docker logs 可以查看某个容器内的日志情况。 前置参数说明 c_name容器名称 / 容器ID logs 获取容器的日志 , 命令如下: docker logs [options] c_name option参数: -n 查看最近多少条记录:docker logs -n 5 c_name--tail与-n 一样 &#…...
Ceph入门到精通-Ceph PG状态详细介绍(全)
本文主要介绍PG的各个状态,以及ceph故障过程中PG状态的转变。 Placement Group States(PG状态) creating Ceph is still creating the placement group. Ceph 仍在创建PG。activating The placement group is peered but not yet active.…...
【数据结构】二叉树、二叉搜索树、平衡二叉树、红黑树、B树、B+树
概述 二叉树(Binary Tree):每个节点最多有两个子节点(左子节点和右子节点),没有限制节点的顺序。特点是简单直观,易于实现,但查找效率较低。 二叉搜索树(Binary Search…...
【JVM】(二)深入理解Java类加载机制与双亲委派模型
文章目录 前言一、类加载过程1.1 加载(Loading)1.2 验证(Verification)1.3 准备(Preparation)1.4 解析(Resolution)1.5 初始化(Initialization) 二、双亲委派…...
npm i 报错项目启动不了解决方法
1.场景 在另一台电脑低版本node环境跑的react项目,换到另一台电脑node18环境执行npm i时候报错 2.解决方法 脚本前加上set NODE_OPTIONS--openssl-legacy-provider...
【从零开始学习JAVA | 第三十七篇】初识多线程
目录 前言: 编辑 引入: 多线程: 什么是多线程: 多线程的意义: 多线程的应用场景: 总结: 前言: 本章节我们将开始学习多线程,多线程是一个很重要的知识点ÿ…...
微信新功能,你都知道吗?
近日iOS 微信8.0.40正式版来了,一起来看看有哪些变化? 1、朋友圈置顶 几个月前微信开始内测「朋友圈置顶」功能,从网友们的反馈来看,iOS 微信 8.0.40 似乎扩大了内测范围,更多用户可以体验到该功能了。 大家可以去自己…...
Android 中 app freezer 原理详解(二):S 版本
基于版本:Android S 0. 前言 在之前的两篇博文《Android 中app内存回收优化(一)》和 《Android 中app内存回收优化(二)》中详细剖析了 Android 中 app 内存优化的流程。这个机制的管理通过 CachedAppOptimizer 类管理,为什么叫这个名字,而不…...
Vue3_04_ref 函数和 reactive 函数
ref 函数 声明变量时,赋值的值要写在 ref() 函数中修改变量时,变量名.value xxx在模板中使用时可以省略掉 .value,直接使用变量名即可 <template><h1>一个人的信息</h1><h2>姓名:{{name}}</h2><…...
05 Ubuntu下安装.deb安装包方式安装vscode,snap安装Jetbrains产品等常用软件
使用deb包安装类型 deb包指的其实就是debian系统,ubuntu系统是基于debian系统的发行版。 一般我们会到需要的软件官网下载deb安装包,然后你既可以采用使用“软件安装”打开的方法来进行安装,也可以使用命令行进行安装。我推荐后者ÿ…...
性能测试jmeter连接数据库jdbc(sql server举例)
一、下载第三方工具包驱动数据库 1. 因为JMeter本身没有提供链接数据库的功能,所以我们需要借助第三方的工具包来实现。 (有这个jar包之后,jmeter可以发起jdbc请求,没有这个jar包,也有jdbc取样器,但不能发起…...
8.3 C高级 Shell脚本
写一个脚本,包含以下内容: 显示/etc/group文件中第五行的内容创建目录/home/ubuntu/copy切换工作路径到此目录赋值/etc/shadow到此目录,并重命名为test将当前目录中test的所属用户改为root将test中其他用户的权限改为没有任何权限 #!/bin/b…...
2023年华数杯A题
A 题 隔热材料的结构优化控制研究 新型隔热材料 A 具有优良的隔热特性,在航天、军工、石化、建筑、交通等 高科技领域中有着广泛的应用。 目前,由单根隔热材料 A 纤维编织成的织物,其热导率可以直接测出;但是 单根隔热材料 A 纤维…...
【零基础学Rust | 基础系列 | 函数,语句和表达式】函数的定义,使用和特性
文章标题 简介一,函数1,函数的定义2,函数的调用3,函数的参数4,函数的返回值 二,语句和表达式1,语句2,表达式 总结: 简介 在Rust编程中,函数,语句…...
加解密算法+压缩工具
sha256 工具类 package com.fanghui.vota.packages.util;import org.slf4j.Logger; import org.slf4j.LoggerFactory;import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.math.BigInteger…...
FeignClient接口的几种方式总结
FeignClient这个注解,已经封装了远程调用协议。在springboot的开发,或者微服务的开发过程中,我们需要跨服务调用,或者调用外部的接口,我们都可以使用FeignClient。 一、FeignClient介绍 FeignClient 注解是 Spring Cl…...
springBoot多数据源使用tdengine(3.0.7.1)+MySQL+mybatisPlus+druid连接池
一、安装部署 1、我这里使用的 3.0.7.1版本,因为我看3.x版本已经发布了一年了,增加了很多新的功能,而且3.x官方推荐,对于2.x的版本,官网都已经推荐进行升级到3.x,所以考虑到项目以后的发展,决定…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...
门静脉高压——表现
一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构:由肠系膜上静脉和脾静脉汇合构成,是肝脏血液供应的主要来源。淤血后果:门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血,引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...
