当前位置: 首页 > 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;可以在本地或远程…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

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>…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...