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,所以考虑到项目以后的发展,决定…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
