【算法与数据结构】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#对象有什么区别? 构造函数 什么是构造方法? 如何使用构造方法? 如何添加成员? 对象的动态成员 正则…...
微信小程序社区户口管理的系统设计与实现
摘要 我国的户口管理制度由来已久,我国对于合法居民在新生儿的出生、户口的落地、迁移以及户口的注销上都有着详细的管理条例进行约束。通过户口的管理可以更好地对我国的居民人数进行有效的内容统计,在进行人口普查的过程中也能够实现更好的、更加精准的…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
