当前位置: 首页 > 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】算法时需要…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...