( “树” 之 DFS) 404. 左叶子之和 ——【Leetcode每日一题】

news/2024/4/19 20:16:50/

404. 左叶子之和

给定二叉树的根节点 root ,返回所有左叶子之和。

示例 1:

在这里插入图片描述

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

示例 2:

在这里插入图片描述

输入: root = [1]
输出: 0

提示:

  • 节点数在 [1, 1000] 范围内
  • -1000 <= Node.val <= 1000

思路:DFS

因为我们求的是左叶子节点之和,所以我们要先判断哪个是左叶子节点;

  • 题目中的示例2表明只有根节点,虽然也是叶子节点,但不算左叶子节点;
  • 所以左叶子节点的条件就是在根节点root节点左边,且是叶子节点,这样我们就能判断左叶子节点了
  • 只需要取出左叶子节点的val值,累加即可;
  • 如果不是左叶子节点,则向下递归。

代码:(Java、C++)

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int sumOfLeftLeaves(TreeNode root) {if(root == null) return 0;int ans = 0;if(root.left != null && root.left.left == null && root.left.right == null){ans = root.left.val;}else{ans = sumOfLeftLeaves(root.left);}return  ans + sumOfLeftLeaves(root.right);}
}

C++

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int sumOfLeftLeaves(TreeNode root) {if(root == null) return 0;int ans = 0;if(root.left != null && root.left.left == null && root.left.right == null){ans = root.left.val;}else{ans = sumOfLeftLeaves(root.left);}return  ans + sumOfLeftLeaves(root.right);}
}

运行结果:

在这里插入图片描述

复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 是树中的节点个数
  • 空间复杂度 O ( n ) O(n) O(n)。空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下,树呈现链式结构,深度为 n ,对应的空间复杂度也为 O ( n ) O(n) O(n)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/45450.html

相关文章

01-智能计算系统概述

一、寒武纪开创了深度学习处理器方向 (1)2007:开始智能和芯片交叉研究 (2)2013:国际首个深度学习处理器架构 获得了CCF A类会议ASPLOS’14最佳论文;亚洲首获体系结构四大顶会最佳论文。 (3)2014:国际首个多核深度学习处理器架构 获得 CCF A类会议MICRO’14最佳论…

vue打包之后,可以进行修改配置后端地址、端口等信息方法

前言 用vue-cli构建的项目通常是采用前后端分离的开发模式&#xff0c;也就是前端与后台完全分离&#xff0c;此时就需要将后台接口地址打包进项目中&#xff0c;但是&#xff0c;难道我们只是改个接口地址也要重新打包吗&#xff1f;当然不行了&#xff0c;那就太麻烦了&#…

Vue 3 第十一章:组件二(组件通信)

文章目录 1. 组件的通信1.1. 父子组件之间的通信1.1.1 父组件向子组件传值1.1.2. 子组件向父组件传值 1.2. 兄弟组件之间的通信1.2.1. 安装1.2.2. 注册1.2.3. 使用 1.3. 跨级组件之间的通信1.3.1 provide/inject 1.4. 非父子组件之间的通信1.4.1. Vuex/Pinia 总结 1. 组件的通信…

软考 软件设计师上午题面向对象

面向过程和面向对象 省略面向对象可以省略过程&#xff0c;复杂事情简单化 类 类是对象的抽象&#xff0c;对象是类的实例 一般类是交通工具。特殊类是轮船飞机。因为他们是特殊的佳通工具&#xff0c;一个天上的一个海上的 对象 属性别名状态成员变量&#xff0c;方法也叫…

轻松掌握微服务治理的注册中心Eureka到Nacos知识点

1、SpringCloud 1、介绍 2、消费者与服务者 3、服务拆分 1、介绍 2、服务之间调用 例如有两个微服务&#xff0c;分别提供用户信息和订单信息。两个服务都有自己的数据库&#xff0c;所以如下查订单信息是不能直接去查用户信息的数据库的&#xff0c;只能从订单服务发起远程…

L2-030 冰岛人

2018年世界杯&#xff0c;冰岛队因1:1平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字后面似乎都有个“松”&#xff08;son&#xff09;&#xff0c;于是有网友科普如下&#xff1a; 冰岛人沿用的是维京人古老的父系姓制&#xff0c;孩子的姓等于父亲的名加后缀&#x…

“科技助力财富增值 京华四季伴您一生”,北银理财深化线下线上客户交流互动

2023年4月12日&#xff0c;北银理财有限责任公司&#xff08;以下简称“北银理财”&#xff09;携手东方财富网启动北银理财财富号&#xff0c;首次采用线上直播及线下主题演讲相结合的方式&#xff0c;在上海举办以“科技助力财富增值&#xff0c;京华四季伴您一生”为主题的机…

华科超算用户手册的学习笔记

1. 资源计费 1.1 费用记账 日期费用&#xff08;上限3000元&#xff09;2023.04.171002023.04.18200总计300 1.2 创建实例时显示项目的余额不足 这是因为项目账户之中目前还没有足够的卡时&#xff1b; Note 这里是因为上次充值的卡时还在田老师的个人账户中&#xff0c;还需…

code=45, title=禁止登录, message=登录失败,建议升级最新版本后重试,或通过问题反馈与我们联系。

如果你是采用 java 开发的&#xff0c;你可以参考本文章&#xff0c;java 和 kotlin 都是可以相互转换的。 在解决之前&#xff0c;先说明环境: JDK版本&#xff1a;java version "17.0.3.1" 【Oracle JDK】 Kotlin版本&#xff1a;1.8.20 采取simbot核心包开发&am…

单片机的实例——28BYJ48步进电机

整体过程 准备资料1&#xff0c;步进电机内部结构示意图2&#xff0c;步进电机命名3&#xff0c;实际结构的转速比4&#xff0c;数值的含义5&#xff0c;实际内部主动轮结构分析实际内部机构及接线定子部分转子部分 定子和转子磁极的工作分析 6&#xff0c;工作时序7&#xff0…

JVM之GC日志解读

通过阅读Gc日志&#xff0c;我们可以了解Java虚拟机内存分配与回收策略。 内存分配与垃圾回收的参数列表 -XX:PrintGC 输出GC日志。类似&#xff1a;-verbose:gc -XX:PrintGCDetails 输出GC的详细日志 -XX:PrintGCTimestamps 输出GC的时间戳&#xff08;以基准时间的形式&#…

centos7 切换上海时间或北京时间

centos7 切换上海时间 要将 CentOS 7 系统的时区更改为上海时间&#xff0c;请按照以下步骤操作&#xff1a; 首先&#xff0c;打开终端并使用 root 用户身份登录&#xff0c;或使用普通用户执行 sudo 命令。 若要查看当前的系统时区&#xff0c;请执行以下命令&#xff1a; …

Web自动化测试怎么做?Web自动化测试的详细流程和步骤

一、什么是web自动化测试 自动化&#xff08;Automation&#xff09;是指机器设备、系统或过程&#xff08;生产、管理过程&#xff09;在没有人或较少人的直接参与下&#xff0c;按照人的要求&#xff0c;经过自动检测、信息处理、分析判断、操纵控制&#xff0c;实现预期的目…

idea使用之 单词拼写检查设置 分级管理

前言 idea的智能提示使用起来非常顺手, 拼接检查也是其中一项, 有些字段什么的, 不小心将单词的字母顺序写错了, idea的拼接检查就会提示(前提是字段命名规范,并且乱序之后的不再是一个具有意义的单词), 如此一来, 就能规避很多粗心大意的错误. 但是呢, 有些时候,项目中有些自…

Java笔记_10(项目阶段----拼图游戏)

项目阶段 页面搭建创建窗口 界面设置和菜单搭建创建菜单 添加图片图片对象 打乱图片用一维数组添加值到二维数组中 事件美化页面移动图片查看完整图片&#xff0c;作弊器&#xff0c;判断胜利计步器和菜单业务的实现弹窗创建 更换图片和登陆页面的建立表单 所有源码的实现游戏规…

RabbitMQ 安装体验

前言 RabbitMQ是一个开源的遵循 AMQP协议实现的基于 Erlang语言编写&#xff0c;即需要先安装部署Erlang环境再安装RabbitMQ环境。 一、Erlang下载安装 https://packagecloud.io/rabbitmq/erlang 上执行命令 此时&#xff0c;Erlang的rpm包下载完成&#xff0c;见下图。 wg…

物联网安全测试

物联网安全测试 尽管物联网&#xff08;IoT&#xff09;重新定义了我们的生活并带来了很多好处&#xff0c;但它的攻击面很大&#xff0c;并且在安全之前是不安全的。如果没有适当的保护&#xff0c;物联网设备很容易成为网络犯罪分子和黑客的目标。您可能会遇到财务和机密数据…

[图神经网络]PyTorch简单实现一个GCN

Pytorch自带一个PyG的图神经网络库&#xff0c;和构建卷积神经网络类似。不同于卷积神经网络仅需重构__init__( )和forward( )两个函数&#xff0c;PyTorch必须额外重构propagate( )和message( )函数。 一、环境构建 ①安装torch_geometric包。 pip install torch_geometric …

【算法系列之二叉树I】leetcode226.翻转二叉树

非递归实现前序遍历 力扣题目链接 解决思路 前序遍历&#xff0c;中左右。先放右节点&#xff0c;后放左节点。 Java实现 class Solution {public List<Integer> preorderTraversal(TreeNode root) {//中左右Stack<TreeNode> stack new Stack<>();List…

九龙证券|服务器龙头获资金连续抢筹,尾盘主力抢筹前期大热门股

今天&#xff0c;核算机职业取得主力大手笔抢筹。 今天主力资金净流出53.89亿元&#xff0c;其间创业板净流出3.19亿元&#xff0c;沪深300成份股净流出7.61亿元。 申万一级职业中&#xff0c;今天有19个职业上涨&#xff0c;传媒职业接连两日均涨近5%&#xff0c;居首位&…