当前位置: 首页 > news >正文

二叉树题目:左叶子之和

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:左叶子之和

出处:404. 左叶子之和

难度

3 级

题目描述

要求

给你二叉树的根结点 root \texttt{root} root,返回所有左叶子之和。

示例

示例 1:

示例 1

输入: root = [3,9,20,null,null,15,7] \texttt{root = [3,9,20,null,null,15,7]} root = [3,9,20,null,null,15,7]
输出: 24 \texttt{24} 24
解释:二叉树中有两个左叶子,结点值分别是 9 \texttt{9} 9 15 \texttt{15} 15

示例 2:

输入: root = [1] \texttt{root = [1]} root = [1]
输出: 0 \texttt{0} 0

数据范围

  • 树中结点数目在范围 [1, 1000] \texttt{[1, 1000]} [1, 1000]
  • -1000 ≤ Node.val ≤ 1000 \texttt{-1000} \le \texttt{Node.val} \le \texttt{1000} -1000Node.val1000

解法一

思路和算法

为了计算左叶子之和,需要找到二叉树中的所有是左子结点的叶结点并计算这些结点之和。可以使用深度优先搜索实现。

从根结点开始遍历二叉树,对于每个结点,首先判断其左右子结点是否为空,然后对非空子结点执行如下操作。

  • 如果左子结点不为空,当左子结点是叶结点时将左子结点的值加到左叶子之和,当左子结点不是叶结点时在左子树中继续遍历。

  • 如果右子结点不为空且不是叶结点,则在右子树中继续遍历。

上述过程是一个递归的过程,递归的终止条件是当前结点为叶结点或者当前结点的非空子结点都为叶结点,其余情况都会调用递归。由于只有在访问到的结点的左子结点是叶结点的情况下才会将左子结点值加到左叶子之和,因此可以确保每个左叶子都被计算一次且其他结点都不会被计算。

代码

class Solution {public int sumOfLeftLeaves(TreeNode root) {int sum = 0;if (root.left != null) {if (isLeaf(root.left)) {sum += root.left.val;} else {sum += sumOfLeftLeaves(root.left);}}if (root.right != null && !isLeaf(root.right)) {sum += sumOfLeftLeaves(root.right);}return sum;}public boolean isLeaf(TreeNode node) {return node.left == null && node.right == null;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点都被访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间,取决于二叉树的高度,最坏情况下二叉树的高度是 O ( n ) O(n) O(n)

解法二

思路和算法

也可以使用广度优先搜索计算左叶子之和。

广度优先搜索需要使用队列存储待访问的结点,初始时将根结点入队列。每次将一个结点出队列,首先判断其左右子结点是否为空,然后对非空子结点执行如下操作。

  • 如果左子结点不为空,当左子结点是叶结点时将左子结点的值加到左叶子之和,当左子结点不是叶结点时将左子结点入队列。

  • 如果右子结点不为空且不是叶结点,则将右子结点入队列。

当队列为空时遍历结束,此时即可得到左叶子之和。

由于只有在访问到的结点的左子结点是叶结点的情况下才会将左子结点值加到左叶子之和,因此可以确保每个左叶子都被计算一次且其他结点都不会被计算。

代码

class Solution {public int sumOfLeftLeaves(TreeNode root) {int sum = 0;Queue<TreeNode> queue = new ArrayDeque<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();if (node.left != null) {if (isLeaf(node.left)) {sum += node.left.val;} else {queue.offer(node.left);}}if (node.right != null) {if (!isLeaf(node.right)) {queue.offer(node.right);}}}return sum;}public boolean isLeaf(TreeNode node) {return node.left == null && node.right == null;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点都被访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是队列空间,队列内元素个数不超过 n n n

相关文章:

二叉树题目:左叶子之和

文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;左叶子之和 出处&#xff1a;404. 左叶子之和 难度 3 级 题目描述 要求 给你二叉树的根结点 root \texttt{ro…...

Spark SQL报错: Task failed while writing rows.

错误 今天运行 Spark 任务时报了一个错误&#xff0c;如下所示&#xff1a; WARN scheduler.TaskSetManager: Lost task 9.0 in stage 3.0 (TID 69, xxx.xxx.xxx.com, executor 3): org.apache.spark.SparkException: Task failed while writing rows.at org.apache.spark.sq…...

Linux系统下U盘打不开: No application is registered as handling this file

简述 系统是之前就安装好使用的Ubuntu14.04&#xff0c;不过由于某些原因只安装到了机械硬盘中&#xff1b;最近新买了一块固态硬盘&#xff0c;所以打算把Ubuntu系统迁移到新的固态硬盘上&#xff1b; 当成功的迁移了系统之后发现其引导有点问题&#xff0c;导致多个系统启动不…...

07 定时器处理非活动连接(上)

07 定时器处理非活动连接&#xff08;上&#xff09; 基础知识 非活跃&#xff0c;是指客户端&#xff08;这里是浏览器&#xff09;与服务器端建立连接后&#xff0c;长时间不交换数据&#xff0c;一直占用服务器端的文件描述符&#xff0c;导致连接资源的浪费。 定时事件&a…...

python——案例四:判断字符串中的元素组成

案例四&#xff1a;判断字符串中的元素组成str"Hello World! 666" print(str.isalnum()) #判读所有的字符都是数字或者是字母 print(str.isalpha()) #判读所有的字符都是字母 print(str.isdigit()) #判读所有的字符都是数字 print(str.islower()) #判读所有的字符都是…...

一起学算法(插入排序篇)

概念&#xff1a; 插入排序&#xff08;inertion Sort&#xff09;一般也被称为直接插入排序&#xff0c;是一种简单的直观的排序算法 工作原理&#xff1a;将待排列元素划分为&#xff08;已排序&#xff09;和&#xff08;未排序&#xff09;两部分&#xff0c;每次从&…...

JVM基础篇-本地方法栈与堆

JVM基础篇-本地方法栈与堆 本地方法栈 什么是本地方法? 本地方法即那些不是由java层面实现的方法&#xff0c;而是由c/c实现交给java层面进行调用&#xff0c;这些方法在java中使用native关键字标识 public native int hashCode()本地方法栈的作用? 为本地方法提供内存空…...

防雷保护区如何划分,防雷分区概念LPZ介绍

在防雷设计中&#xff0c;很重要的一点就是防雷分区的划分&#xff0c;只有先划分好防雷区域等级&#xff0c;才好做出比较好的防雷器设计方案。 因为标准对不同区安装的防雷浪涌保护器要求是不一样的。 那么&#xff0c;防雷保护区是如何划分的呢&#xff1f; 如上图所示&…...

随手笔记——3D−3D:ICP求解

随手笔记——3D−3D&#xff1a;ICP求解 使用 SVD 求解 ICP使用非线性优化来求解 ICP 原理参见 https://blog.csdn.net/jppdss/article/details/131919483 使用 SVD 求解 ICP 使用两幅 RGB-D 图像&#xff0c;通过特征匹配获取两组 3D 点&#xff0c;最后用 ICP 计算它们的位…...

Python调用各大机器翻译API大全

过去的二三年中&#xff0c;我一直关注的是机器翻译API在自动化翻译过程中的应用&#xff0c;包括采用CAT工具和Python编程语言来调用机器翻译API&#xff0c;然后再进行译后编辑&#xff0c;从而达到快速翻译的目的。 然而&#xff0c;我发现随着人工智能的发展&#xff0c;很…...

重生之我要学C++第六天

这篇文章的主要内容是const以及权限问题、static关键字、友元函数和友元类&#xff0c;希望对大家有所帮助&#xff0c;点赞收藏评论支持一下吧&#xff01; 更多优质内容跳转&#xff1a; 专栏&#xff1a;重生之C启程(文章平均质量分93) 目录 const以及权限问题 1.const修饰…...

SpringBoot中ErrorPage(错误页面)的使用--【ErrorPage组件】

SpringBoot系列文章目录 SpringBoot知识范围-学习步骤–【思维导图知识范围】 文章目录 SpringBoot系列文章目录本系列校训 SpringBoot技术很多很多环境及工具&#xff1a;必要的知识深层一些的知识 上效果图在Spring Boot里使用ErrorPage还要注意的是 配套资源作业&#xff…...

【Android】APP网络优化学习笔记

网络优化原因 进行网络优化对于移动应用程序而言非常重要&#xff0c;原因如下&#xff1a; 用户体验&#xff1a; 网络连接是移动应用程序的核心功能之一。通过进行网络优化&#xff0c;可以提高应用的加载速度和响应速度&#xff0c;减少用户等待时间&#xff0c;提供更流…...

简单的知识图谱可视化+绘制nx.Graph()时报错TypeError: ‘_AxesStack‘ object is not callable

绘制nx.Graph时报错TypeError: _AxesStack object is not callable 写在最前面知识图谱可视化预期报错可能的原因 原代码原因确认解决后的代码解决&#xff01; 写在最前面 实现一个简单的知识图谱的可视化功能。 使用了NetworkX库来构建知识图谱&#xff0c;并使用matplotlib…...

【Matlab】基于粒子群优化算法优化BP神经网络的时间序列预测(Excel可直接替换数据)

【Matlab】基于粒子群优化算法优化BP神经网络的时间序列预测(Excel可直接替换数据) 1.模型原理2.数学公式3.文件结构4.Excel数据5.分块代码5.1 fun.m5.2 main.m6.完整代码6.1 fun.m6.2 main.m7.运行结果1.模型原理 基于粒子群优化算法(Particle Swarm Optimization, PSO)优…...

【机器学习】Cost Function for Logistic Regression

Cost Function for Logistic Regression 1. 平方差能否用于逻辑回归&#xff1f;2. 逻辑损失函数loss3. 损失函数cost附录 导入所需的库 import numpy as np %matplotlib widget import matplotlib.pyplot as plt from plt_logistic_loss import plt_logistic_cost, plt_two_…...

【EI/SCOPUS会议征稿】2023年第四届新能源与电气科技国际学术研讨会 (ISNEET 2023)

作为全球科技创新大趋势的引领者&#xff0c;中国一直在为科技创新创造越来越开放的环境&#xff0c;提高学术合作的深度和广度&#xff0c;构建惠及全民的创新共同体。这些努力为全球化和创建共享未来的共同体做出了新的贡献。 为交流近年来国内外在新能源和电气技术领域的最新…...

【计算机网络】10、ethtool

文章目录 一、ethtool1.1 常见操作1.1.1 展示设备属性1.1.2 改变网卡属性1.1.2.1 Auto-negotiation1.1.2.2 Speed 1.1.3 展示网卡驱动设置1.1.4 只展示 Auto-negotiation, RX and TX1.1.5 展示统计1.1.7 排除网络故障1.1.8 通过网口的 LED 区分网卡1.1.9 持久化配置&#xff08…...

什么是前端工程化?

工程化介绍 什么是前端工程化&#xff1f; 前端工程化是一种思想&#xff0c;而不是某种技术。主要目的是为了提高效率和降低成本&#xff0c;也就是说在开发的过程中可以提高开发效率&#xff0c;减少不必要的重复性工作等。 tip 现实生活举例 建房子谁不会呢&#xff1f;请…...

【深度学习】【三维重建】windows11环境配置tiny-cuda-nn详细教程

【深度学习】【三维重建】windows11环境配置tiny-cuda-nn详细教程 文章目录 【深度学习】【三维重建】windows11环境配置tiny-cuda-nn详细教程前言确定版本对应关系源码编译安装tiny-cuda-nn总结 前言 本人windows11下使用【Instant Neural Surface Reconstruction】算法时需要…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

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…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...