【算法与数据结构】404、LeetCode左叶子之和
文章目录
- 一、题目
- 二、解法
- 三、完整代码
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目
二、解法
思路分析:思路比较简单,遍历所有节点然后判断该节点是否为左叶子节点,如果是,将其值累加。遍历算法采用【算法与数据结构】144、94、145LeetCode二叉树的前中后遍历(递归法、迭代法)文章中递归前序遍历算法,设置了一个左节点标志符,遍历左节点时,标识符为1,左右节点为空则为叶子节点。
程序如下:
class Solution {
public:void traversal_preOrder(TreeNode* cur, int& sum, int left_flag) { // 前序遍历if (cur == NULL) return;if (!cur->left && !cur->right && left_flag) sum += cur->val; // 叶子节点且为左节点traversal_preOrder(cur->left, sum, 1); // 左traversal_preOrder(cur->right, sum, 0); // 右 }// 遍历所有节点,判断每个节点的左节点是否为叶子结点,然后相加int sumOfLeftLeaves(TreeNode* root) { int result = 0;traversal_preOrder(root, result, 0);return result;}
};
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)。
- 空间复杂度: O ( n ) O(n) O(n)。
三、完整代码
# include<iostream>
# include<string>
# include<vector>
# include<queue>
using namespace std;// 树节点定义
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:void traversal_preOrder(TreeNode* cur, int& sum, int left_flag) { // 前序遍历if (cur == NULL) return;if (!cur->left && !cur->right && left_flag) sum += cur->val; // 叶子节点且为左节点traversal_preOrder(cur->left, sum, 1); // 左traversal_preOrder(cur->right, sum, 0); // 右 }// 遍历所有节点,判断每个节点的左节点是否为叶子结点,然后相加int sumOfLeftLeaves(TreeNode* root) { int result = 0;traversal_preOrder(root, result, 0);return result;}
};// 前序遍历迭代法创建二叉树,每次迭代将容器首元素弹出(弹出代码还可以再优化)
void Tree_Generator(vector<string>& t, TreeNode*& node) {if (!t.size() || t[0] == "NULL") return; // 退出条件else {node = new TreeNode(stoi(t[0].c_str())); // 中if (t.size()) {t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->left); // 左}if (t.size()) {t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->right); // 右}}
}// 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size(); // size必须固定, que.size()是不断变化的vector<int> vec;for (int i = 0; i < size; ++i) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;
}template<typename T>
void my_print(T& v, const string msg)
{cout << msg << endl;for (class T::iterator it = v.begin(); it != v.end(); it++) {cout << *it << ' ';}cout << endl;
}template<class T1, class T2>
void my_print2(T1& v, const string str) {cout << str << endl;for (class T1::iterator vit = v.begin(); vit < v.end(); ++vit) {for (class T2::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {cout << *it << ' ';}cout << endl;}
}int main()
{vector<string> t = { "3", "9", "NULL", "NULL", "20", "15", "NULL", "NULL", "7", "NULL", "NULL" }; // 前序遍历my_print(t, "目标树");TreeNode* root = new TreeNode();Tree_Generator(t, root);vector<vector<int>> tree = levelOrder(root);my_print2<vector<vector<int>>, vector<int>>(tree, "目标树:");Solution s;int result = s.sumOfLeftLeaves(root);cout << "sumOfLeftLeaves: " << result << endl;system("pause");return 0;
}
end
相关文章:

【算法与数据结构】404、LeetCode左叶子之和
文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析:思路比较简单,遍历所有节点然后判断该节点是否为左叶子节点,如果是,…...

Apifox下载安装步骤
我们先访问网址 https://apifox.com/?utm_sourcebaidu&utm_mediumsem&utm_campaign251430236&utm_content7810722111&utm_termapifox%E6%9F%A5%E7%9C%8B%E7%89%88%E6%9C%AC&bd_vid8323327349775096324 然后 这里这个免费下载已经写的这么明显了 那就直接点…...
大华摄像头有问题,海康摄像头也有问题
买了个大华摄像头,除了抗噪方面效果不好,我是很满意的。前一段时间摄像头启动出了点问题(忘记拔掉SD卡),于是买了个海康的。 大华摄像头是3寸,海康是2寸。视频效果差多了。看来大有大的道理。更可恨的是&a…...

Linux多线程同步机制(下)
文章目录 前言一、读写锁二、条件变量总结 前言 一、读写锁 多线程同步机制中的读写锁(Read-Write Lock)是一种特殊的锁机制,用于控制对共享资源的读写访问。读写锁允许多个线程同时读取共享资源,但在写操作时需要独占访问。 读…...

【QT】ComboBox的使用(14)
ComboBox这个控件我常用于多文本的储存、调用,正如他的中文意思为:下拉列表框。 下拉列表框:字面意思就是一个多文本的列表框,今天来看下如何使用ComboBox这个控件。 一.环境配置 1.python 3.7.8 可直接进入官网下载安装&…...
关于写英文论文的一些总结
名词连接名词组成名词,例如任务名,用task name,而不是name of task。其他各种词也是类似的;本文提出了什么什么,用 this study;多用it is become xx,这种更好,而不是we xx࿱…...
swagger 2.10.5 整合 spring boot
参考: http://springfox.github.io/springfox/ https://github.com/springfox/springfox http://springfox.github.io/springfox/docs/current/ https://github.com/springfox/springfox-demos https://github.com/springfox/springfox-demos/tree/2.9.2 https://gi…...

Python 练习:剔除数字
练习:剔除数字: 要求如下: 1、编写一段程序代码,程序运行后, 需要用户随意输入一段包含有数字和字母的字符串; 2、程序会自动删除字符串中的数字, 然后输出一串没有数字的字符串(纯…...
Linux系统编程:基础知识入门学习笔记汇总
Linux基础shell编程——>Linux 系统编程——>(计算机网络)——>Linux 网络编程 来源:黑马程序员-Linux系统编程 45小时 评价 这个老师好像讲了很多课程,都还不错我由于赶时间之前学过Linux的Shell编程和Linux的网络编程&…...

基于硬件隔离增强risc-v调试安全1_问题描述
安全之安全(security)博客目录导读 2023 RISC-V中国峰会 安全相关议题汇总 说明:本文参考RISC-V 2023中国峰会如下议题,版权归原作者所有。...

OpenCV简介
OpenCV简介 OpenCV(开源计算机视觉库:http://opencv.org)是一个开源库,包含数百种计算机视觉算法。OpenCV 具有模块化结构,主要包括下列模块: 核心功能(core) - 定义基本数据结构的…...
Windows下编译qt-src-5.15.10
首先从镜像站点下载qt源码: https://download.qt.io/static/mirrorlist/ 下载QT的镜像站点 下载源码后解压到 F: 盘 创建编译目录F:\qtbuild 打开VS2019的 X64 Native Tools Command Prompt for VS 2019 进入到源码目录 cd F:\qt-everywher…...
有关linux排查服务器资源问题
查看 磁盘占用 df -h 进入到某一个文件夹下 查看对应文件夹占用 du -sh /usr...
【设计模式】Head First 设计模式——观察者模式 C++实现
设计模式最大的作用就是在变化和稳定中间寻找隔离点,然后分离它们,从而管理变化。将变化像小兔子一样关到笼子里,让它在笼子里随便跳,而不至于跳出来把你整个房间给污染掉。 设计思想 主题对象(出版者)管理…...

【ES】笔记-Promise基本使用
笔记-基本使用 一、初始Promise1. 抽象表达:2. 具体表达:为什么要用 Promise?promise的基本流程 二、fs读取文件三、AJAX请求四、Promise封装fs模块五、util.promisify方法六、Promise封装AJAX操作 一、初始Promise 1. 抽象表达: 1. Promise 是一门新的技术(ES6 规范) 2. Pr…...

服务器数据恢复-reiserfs文件系统损坏如何恢复数据?
服务器数据恢复环境: 一台IBM X系列服务器,4块SAS硬盘组建一组RAID5阵列,采用的reiserfs文件系统。服务器操作系统分区结构:boot分区LVM卷swap分区(按照前后顺序)。LVM卷中直接划分了一个reiserfs文件系统&…...

直播预告:把脉2023年下半场—主动防御邮箱盗号威胁
长期以来,承载着大量敏感数据的企业是黑产团伙的首要攻击目标。Coremail结合多年以来的邮件防护经验发现,黑产团伙针对企业邮箱账号安全的两大攻击方式为暴力破解和钓鱼邮件攻击。 一、企业邮箱安全现状 01、使用弱密码 企业员工使用弱密码让黑产团伙有…...

专题:平面、空间直线参数方程下的切线斜率问题
本文研究平面、空间直线在参数方程形式下,切线斜率(即导数)如何表示的问题。 如上图所示。 设 y f ( x ) , x φ ( t ) , y ψ ( t ) 当 t t 0 时, x x 0 , y y 0 ,即点 A 坐…...

JavaScript—对象与构造方法
目录 json对象(字面值) js中对象是什么? 如何使用? 关联数组 js对象和C#对象有什么区别? 构造函数 什么是构造方法? 如何使用构造方法? 如何添加成员? 对象的动态成员 正则…...
微信小程序社区户口管理的系统设计与实现
摘要 我国的户口管理制度由来已久,我国对于合法居民在新生儿的出生、户口的落地、迁移以及户口的注销上都有着详细的管理条例进行约束。通过户口的管理可以更好地对我国的居民人数进行有效的内容统计,在进行人口普查的过程中也能够实现更好的、更加精准的…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...