【算法与数据结构】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#对象有什么区别? 构造函数 什么是构造方法? 如何使用构造方法? 如何添加成员? 对象的动态成员 正则…...
微信小程序社区户口管理的系统设计与实现
摘要 我国的户口管理制度由来已久,我国对于合法居民在新生儿的出生、户口的落地、迁移以及户口的注销上都有着详细的管理条例进行约束。通过户口的管理可以更好地对我国的居民人数进行有效的内容统计,在进行人口普查的过程中也能够实现更好的、更加精准的…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...
