当前位置: 首页 > news >正文

【算法与数据结构】513、LeetCode找树左下角的值

文章目录

  • 一、题目
  • 二、解法
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

  思路分析:这道题用层序遍历来做比较简单,最底层最左边节点就是层序遍历当中最底层元素容器的第一个值,层序遍历利用了【算法和数据结构】102、LeetCode二叉树的层序遍历文章中的迭代法,稍加修改就可以实现题目要求。
  程序如下

// 层序遍历迭代法
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);int result = 0;while (!que.empty()) {int size = que.size();  // size必须固定, que.size()是不断变化的for (int i = 0; i < size; ++i) {TreeNode* node = que.front();que.pop();if (i == 0) result = node->val; // 访问容器当中第一个元素if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)

三、完整代码

# include <iostream>
# include <vector>
# include <queue>
# include <string>
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:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);int result = 0;while (!que.empty()) {int size = que.size();  // size必须固定, que.size()是不断变化的for (int i = 0; i < size; ++i) {TreeNode* node = que.front();que.pop();if (i == 0) result = node->val; // 访问容器当中第一个元素if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};void my_print1(vector <string>& v, string msg)
{cout << msg << endl;for (vector<string>::iterator it = v.begin(); it != v.end(); it++) {cout << *it << "  ";}cout << endl;
}void my_print2(vector<vector<int>>& v, string str) {cout << str << endl;for (vector<vector<int>>::iterator vit = v.begin(); vit < v.end(); ++vit) {for (vector<int>::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {cout << *it << ' ';}cout << endl;}
}// 前序遍历递归法创建二叉树,每次迭代将容器首元素弹出(弹出代码还可以再优化)
void Tree_Generator(vector<string>& t, TreeNode*& node) {if (t[0] == "NULL" || !t.size()) return;    // 退出条件else {node = new TreeNode(stoi(t[0].c_str()));    // 中t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->left);              // 左t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->right);             // 右}
}int main()
{vector<string> t = { "3", "9", "NULL", "NULL", "20", "15", "NULL", "NULL", "7", "NULL", "NULL" };   // 前序遍历my_print1(t, "目标树:");TreeNode* root = new TreeNode();Tree_Generator(t, root);Solution s1;int result = s1.findBottomLeftValue(root);cout << "最底层最左边元素为:  " << result <<endl; system("pause");return 0;
}

end

相关文章:

【算法与数据结构】513、LeetCode找树左下角的值

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析&#xff1a;这道题用层序遍历来做比较简单&#xff0c;最底层最左边节点就是层序遍历当中最底层元素容器的第一个值…...

React——组件缓存 react-activation

1、安装依赖 npm i -S react-activation 2、包裹根组件 import { AliveScope } from "react-activation"<AliveScope><App /> </AliveScope> 3、缓存组件 import { KeepAlive } from "react-activation"export default () > {co…...

EV代码签名证书是什么?

在数字世界中&#xff0c;很多软件和应用都需要进行代码签名&#xff0c;以确保其来源可靠和安全&#xff0c;EV代码签名证书恰好都能做到&#xff0c;那么EV代码签名证书是什么&#xff1f;它有什么功能特点呢&#xff1f;下面的内容可以给到答案。 EV代码签名证书是什么&…...

融媒行业落地客户旅程编排,详解数字化用户运营实战

移动互联网时代是流量红利的时代&#xff0c;企业常用低成本的方式进行获客&#xff0c;“增长黑客”的概念大范围传播。与此同时&#xff0c;机构媒体受到传播环境的影响&#xff0c;也开始启动全行业的媒体融合转型。在此背景下&#xff0c;2015 年神策数据成立&#xff0c;核…...

PDF制作成翻页电子书

在日常工作中&#xff0c;大部分人使用的都是PDF文档发送给客户&#xff0c;但是PDF文档通常是静态的&#xff0c;缺乏交互性和视觉吸引力。那你有没有想过把它转换成翻页的电子书呢&#xff1f; 小编将告诉你操作步骤&#xff0c;非常简单 1.搜索FLBOOK在线制作电子杂志平台 …...

多线程

1. 线程池 1.1 线程状态介绍 当线程被创建并启动以后&#xff0c;它既不是一启动就进入了执行状态&#xff0c;也不是一直处于执行状态。线程对象在不同的时期有不同的状态。那么Java中的线程存在哪几种状态呢&#xff1f;Java中的线程 状态被定义在了java.lang.Thread.Stat…...

BingChat与ChatGPT比较,哪个聊天机器人能让你获益更多?

人工智能领域的最新进展为普通人创造新的收入来源提供了更多机会。今年早些时候&#xff0c;微软对OpenAI进行了大量投资。此后&#xff0c;微软在Microsoft Edge浏览器中推出了自家的聊天机器人Bing Chat。 在论坛和社交媒体上&#xff0c;你可以发现这两个AI工具都吸引了很…...

Qt读写ini配置文件(QSettings)、XML

1、ini相关的 总结&#xff1a;Qt读写ini配置文件(QSettings) - 布丁Plus - 博客园 (cnblogs.com) Qt读写ini文件&#xff08;含源码注释&#xff09;_qt ini文件读写_lw向北.的博客-CSDN博客 2、XML相关的 Qt读写XML文件&#xff08;含源码注释&#xff09;_qt写xml_lw向北…...

JVM知识点(二)

1、G1垃圾收集器 -XX:MaxGCPauseMillis10&#xff0c;G1的参数&#xff0c;表示在任意1s时间内&#xff0c;停顿时间不能超过10ms&#xff1b;G1将堆切分成很多小堆区&#xff08;Region&#xff09;&#xff0c;每一个Region可以是Eden、Survivor或Old区&#xff1b;这些区在…...

代码随想录算法训练营day44 | LeetCode 518. 零钱兑换 II 377. 组合总和 Ⅳ

今晚学习了完全背包的做法&#xff0c;和01背包的差别具体来说就是一个可以重复&#xff0c;一个不可以重复。体现在数组的遍历中来说就是完全背包不能用二维数组做法&#xff08;因为二维dp数组一定不会重复&#xff0c;但是还没验证过&#xff09;&#xff0c;只能用一维dp数…...

Vue2向Vue3过度核心技术工程化开发和脚手架

目录 1 工程化开发和脚手架1.1 开发Vue的两种方式1.2.脚手架Vue CLI 2 项目目录介绍和运行流程2.1 项目目录介绍2.2 运行流程 3 组件化开发4 根组件 App.vue4.1 根组件介绍4.2 组件是由三部分构成4.3 总结 5 普通组件的注册使用-局部注册5.1 特点&#xff1a;5.2 步骤&#xff…...

Expected all tensors to be on the same device, but found at least two devices

Expected all tensors to be on the same device, but found at least two devices, 原因是计算的过程中&#xff0c;两个不同类型的变量在一起进行运算&#xff0c;即一个变量存储在gpu中&#xff0c;一个变量存储在cpu中&#xff0c;两个变量的存储位置冲突&#xff0c;导致无…...

Mysql备份命令Mysqldump导入、导出以及压缩成zip、gz格式

1、导出 命令&#xff1a;mysqldump -u用户名 -p数据库密码 数据库名 > 文件名 如果用户名需要密码&#xff0c;则需要在此命令执行后输入一次密码核对&#xff1b;如果数据库用户名不需要密码&#xff0c;则不要加“-p”参数&#xff0c;导入的时候相同。注意输入的用户名…...

App卡帧与BlockCanary

作者&#xff1a;图个喜庆 一&#xff0c;前言 app卡帧一直是性能优化的一个重要方面&#xff0c;虽然现在手机硬件性能越来越高&#xff0c;明显的卡帧现象越来越少&#xff0c;但是了解卡帧相关的知识还是非常有必要的。 本文分两部分从app卡帧的原理出发&#xff0c;讨论屏…...

bpmnjs Properties-panel拓展(ExtensionElements拓展篇)

接上文bpmnjs Properties-panel拓展&#xff08;属性设置篇&#xff09;&#xff0c;继续记录下第三个拓展需求的实现。 需求简述 在ExclusiveGateway标签的extensionElements标签中增加子标签<activiti:executionListener>子标签&#xff0c;可增加复数子标签。子标签…...

虚拟机的使用

首先需要安装VMware软件&#xff0c;这是虚拟机&#xff0c;在里面可以实现在windows的笔记本上运行包括&#xff0c;windows11和linux系统的开发和研究。 VMware是一种虚拟化技术&#xff0c;可以让你在一台物理计算机上运行多个操作系统和应用程序&#xff0c;而不需要重启或…...

CSS Flex布局

前言 Flex布局&#xff08;弹性盒子布局&#xff09; 是一种用于在容器中进行灵活和自适应布局的CSS布局模型。通过使用Flex布局&#xff0c;可以更方便地实现各种不同尺寸和比例的布局&#xff0c;使元素在容器内自动调整空间分配。 Flex-组成 Flex布局由以下几个主要组成部分…...

Virtual

虚拟接口可以用作编写操作系统和驱动程序独立测试的一种方式。任何连接到同一通道(来自同一Python进程)的VirtualBus实例都将相互接收消息。 如果消息应跨进程或主机边界发送,请考虑使用多播IP接口,并参考虚拟接口对不同虚拟接口进行比较和一般性讨论。 Example import …...

6、监测数据采集物联网应用开发步骤(5.2)

监测数据采集物联网应用开发步骤(5.1) 包含4个类数据库连接&#xff08;com.zxy.db_Self.ConnectionPool_Self.py&#xff09;、数据库操作类&#xff08;com.zxy.db_Self.Db_Common_Self.py&#xff09;、数据库管理类&#xff08;com.zxy.db_Self.DBManager_Self.py&#xf…...

解释 Git 的基本概念和使用方式

该文为AI自动生成&#xff0c;InsCode AI 创作助手 Git 是一种版本控制工具&#xff0c;用于跟踪代码或文件的更改历史记录。以下是 Git 的基本概念和使用方式&#xff1a; 仓库 (Repository)&#xff1a;仓库是一个存储项目代码和历史记录的地方&#xff0c;可以在本地或远程…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...