【算法与数据结构】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#对象有什么区别? 构造函数 什么是构造方法? 如何使用构造方法? 如何添加成员? 对象的动态成员 正则…...
微信小程序社区户口管理的系统设计与实现
摘要 我国的户口管理制度由来已久,我国对于合法居民在新生儿的出生、户口的落地、迁移以及户口的注销上都有着详细的管理条例进行约束。通过户口的管理可以更好地对我国的居民人数进行有效的内容统计,在进行人口普查的过程中也能够实现更好的、更加精准的…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
