LeetCode 513.找树左下角的值

LeetCode 513.找树左下角的值

1、题目

题目链接：513. 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

示例 1:
image.png

输入: root = [2,1,3]
输出: 1

示例 2:
image.png

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

  • 二叉树的节点个数的范围是 [1,104]
  • -231 <= Node.val <= 231 - 1

2、深度优先搜索（递归）

思路

这道题要在二叉树的 最后一行 找到 最左边的值。
如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。所以要找深度最大的叶子节点。
那么如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。
我们使用 maxDepth 用来记录最大深度，result 记录最大深度最左节点的数值。
在写递归时，我们要先明确递归三部曲：

  1. 确定递归函数的参数和返回值

参数必须有要遍历的树的根节点，depth 用来记录当前深度，maxDepth 用来记录最大深度，result 记录最大深度最左节点的数值。 这里就不需要返回值了，所以递归函数的返回类型为 void。
代码如下：

void traversal(TreeNode* root, int depth, int& maxDepth, int& result)
  1. 确定终止条件

当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。
代码如下：

// 如果当前节点是叶子节点
if (root->left == nullptr && root->right == nullptr) {// 如果当前深度大于最大深度if (depth > maxDepth) {// 更新最大深度maxDepth = depth;// 更新结果值为当前节点的值result = root->val;}return;
}
  1. 确定单层递归的逻辑

在找最大深度的时候，递归的过程中依然要使用回溯。
代码如下：

// 如果左子节点存在
if (root->left) {// 深度加1depth++;// 递归遍历左子树traversal(root->left, depth, maxDepth, result);// 回溯，深度减1depth--;
}
// 如果右子节点存在
if (root->right) {// 深度加1depth++;// 递归遍历右子树traversal(root->right, depth, maxDepth, result);// 回溯，深度减1depth--;
}

代码

#include <iostream>
#include <climits>using namespace std;//Definition for a binary tree node.
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(TreeNode* root, int depth, int& maxDepth, int& result) {// 如果当前节点是叶子节点if (root->left == nullptr && root->right == nullptr) {// 如果当前深度大于最大深度if (depth > maxDepth) {// 更新最大深度maxDepth = depth;// 更新结果值为当前节点的值result = root->val;}return;}// 如果左子节点存在if (root->left) {// 深度加1depth++;// 递归遍历左子树traversal(root->left, depth, maxDepth, result);// 回溯，深度减1depth--;}// 如果右子节点存在if (root->right) {// 深度加1depth++;// 递归遍历右子树traversal(root->right, depth, maxDepth, result);// 回溯，深度减1depth--;}return;}int findBottomLeftValue(TreeNode* root) {if (root == nullptr) {return 0;}// 记录最大深度int maxDepth = INT_MIN;// 记录最大深度最左节点的数值int result = 0;traversal(root, 0, maxDepth, result);return result;}
};int main() {Solution s;TreeNode* root = new TreeNode(3);root->left = new TreeNode(9);root->right = new TreeNode(20);root->right->left = new TreeNode(15);root->right->right = new TreeNode(7);cout << s.findBottomLeftValue(root) << endl;return 0;
}

复杂度分析

  • 时间复杂度: O(n)，其中 n 是二叉树的节点数目。需要遍历 n 个节点。
  • 空间复杂度: O(n)。递归栈需要占用 O(n) 的空间。

3、深度优先搜索（递归精简版）

思路

在回溯的地方可以进行精简，在调用traversal函数时，depth加1，在递归结束时再减1，以确保在递归的不同层次上深度值是正确的。
代码如下：
traversal(root->right, depth + 1, maxDepth, result);

代码

class Solution {
public:void traversal(TreeNode* root, int depth, int& maxDepth, int& result) {// 如果当前节点是叶子节点if (root->left == nullptr && root->right == nullptr) {// 如果当前深度大于最大深度if (depth > maxDepth) {// 更新最大深度maxDepth = depth;// 更新结果值为当前节点的值result = root->val;}return;}// 如果左子节点存在if (root->left) {// 递归遍历左子树，这里隐藏了回溯操作，在调用traversal函数时，depth加1，在递归结束时再减1traversal(root->left, depth + 1, maxDepth, result);}// 如果右子节点存在if (root->right) {// 递归遍历右子树，这里隐藏了回溯操作，在调用traversal函数时，depth加1，在递归结束时再减1traversal(root->right, depth + 1, maxDepth, result);}return;}int findBottomLeftValue(TreeNode* root) {if (root == nullptr) {return 0;}// 记录最大深度int maxDepth = INT_MIN;// 记录最大深度最左节点的数值int result = 0;traversal(root, 0, maxDepth, result);return result;}
};

复杂度分析

  • 时间复杂度: O(n)，其中 n 是二叉树的节点数目。需要遍历 n 个节点。
  • 空间复杂度: O(n)。递归栈需要占用 O(n) 的空间。

4、广度优先搜索（正向层序遍历）

思路

使用广度优先搜索遍历每一层的节点。遍历到最后一行的第一个结点就是要找的结点。

代码

class Solution {
public:int findBottomLeftValue(TreeNode* root) {// 如果根节点为空，返回0if (root == nullptr) {return 0;}// 创建一个队列用于层序遍历queue<TreeNode*> que;// 记录结果int result = 0;// 将根节点入队que.push(root);// 当队列不为空时，进行循环while (!que.empty()) {// 获取当前层的节点个数int 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)

5、广度优先搜索（逆向层序遍历）

思路

使用广度优先搜索遍历每一层的节点。在遍历一个节点时，需要先把它的非空右子节点放入队列，然后再把它的非空左子节点放入队列，这样才能保证从右到左遍历每一层的节点。广度优先搜索所遍历的最后一个节点的值就是最底层最左边节点的值。

代码

class Solution {
public:int findBottomLeftValue(TreeNode* root) {// 如果根节点为空，返回0if (root == nullptr) {return 0;}// 创建一个队列用于层序遍历queue<TreeNode*> que;// 记录结果int result = 0;// 将根节点入队que.push(root);// 当队列不为空时，进行循环while (!que.empty()) {// 获取队首节点TreeNode* node = que.front();que.pop();// 如果该节点有右子节点，将右子节点入队if (node->right) {que.push(node->right);}// 如果该节点有右子节点，将右子节点入队if (node->left) {que.push(node->left);}// 更新结果为当前节点的值result = node->val;}return result;}
};

复杂度分析

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

http://www.ppmy.cn/ops/40846.html

相关文章

2-6 任务 猜数小游戏（单次版）

2-6 任务 猜数小游戏（单次版）

本任务要求编写一个猜数小游戏&#xff08;单次版&#xff09;&#xff0c;游戏规则是计算机产生一个0到100之间的随机整数&#xff0c;用户通过输入猜测的数字进行猜测&#xff0c;根据猜测情况给出提示&#xff0c;直到猜对为止。编程思路是利用while循环和多分支结构实现永真…
阅读更多...
SSH 免密登录，设置好仍然需要密码登录解决方法

SSH 免密登录，设置好仍然需要密码登录解决方法

说明&#xff1a; ssh秘钥登录设置好了&#xff0c;但是登录的时候依然需要提供密码 查看系统安全日志&#xff0c;定位问题 sudo cat /var/log/auth.log或者 sudo cat /var/log/secure找到下面的信息 Authentication refused: bad ownership or modes...&#xff08;网上的…
阅读更多...
STM32 FreeRTOS 常用API

STM32 FreeRTOS 常用API

任务间同步 1&#xff0c;信号量 信号量分为二进制信号量 和计数型信号量 信号&#xff1a;起通知作用 量&#xff1a;还可以用来表示资源的数量 当"量"没有限制时&#xff0c;它就是"计数型信号量"(Counting Semaphores) 当"量"只有0、1两…
阅读更多...
004.可观察对象与观察者

004.可观察对象与观察者

Rx非常适合事件驱动的应用程序。这是有意义的&#xff0c;因为事件(作为)(如前所述)是创建时变值的命令式方法。从历史上看,事件驱动编程主要出现在客户端技术中&#xff0c;因为作为事件实现的用户交互。例如&#xff0c;你可能工作过使用OnMouseMove或OnKeyPressed事件。正因…
阅读更多...
css 步骤条虚线渐变色效果实现

css 步骤条虚线渐变色效果实现

效果如图所示&#xff1a; 思路&#xff1a; 使用元素覆盖的方式实现视觉上虚线的效果 实现代码&#xff1a; html布局 <ul class"details-cont"><li class"details-li" v-for"item in 3" :key"item"><div class&qu…
阅读更多...
WHAT - CSS Animationtion 动画系列（一）

WHAT - CSS Animationtion 动画系列（一）

目录 一、介绍二、animation-name三、animation-duration四、animation-timing-function4.1 介绍4.2 具体实践&#xff1a;抛物线 五、animation-delay六、animation-iteration-count七、animation-direction八、animation-fill-mode九、animation-play-state 今天我们主要学习…
阅读更多...
Java后端的接口参数两个interger 类型情况解决

Java后端的接口参数两个interger 类型情况解决

get请求 &#xff0c;对应请求头 RequestParm, post请求&#xff0c; 对应请求体 &#xff0c;RequestBody 两个Integer参数情况 GetMapping("/insertStaffClass")public R<Void> insertStaffClass(RequestParam Integer staffId,RequestParam List<Integ…
阅读更多...
Flutter 中的 CircleAvatar 小部件：全面指南

Flutter 中的 CircleAvatar 小部件：全面指南

Flutter 中的 CircleAvatar 小部件&#xff1a;全面指南 在 Flutter 中&#xff0c;CircleAvatar 是一个用于显示头像的圆形控件&#xff0c;通常包含一个图标、图片或者一个简单的文本字符。它在设计上与 Material Design 指南中的头像规范相匹配&#xff0c;常用于展示用户信…
阅读更多...
【全开源】预约咨询小程序基于Fastadmin+ThinkPHP和Uniapp

【全开源】预约咨询小程序基于Fastadmin+ThinkPHP和Uniapp

功能介绍 基于FastadminThinkPHP和Uniapp开发的预约咨询系统&#xff0c;可应用于心理咨询、问诊、法律咨询等咨询类场景。 功能 1.后台可维护咨询师。 2.可以设置可预约的时间段。 3.可增加特殊时间不可预约&#xff0c;例如节假日。 4.可自定义擅长领域 5.可以自定义预约类…
阅读更多...
C语言（指针）6

C语言（指针）6

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸各位能阅读我的文章&#xff0c;诚请评论指点&#xff0c;关注收藏&#xff0c;欢迎欢迎~~ &#x1f4a5;个人主页&#xff1a;小羊在奋斗 &#x1f4a5;所属专栏&#xff1a;C语言 本系列文章为个人学习笔记&#x…
阅读更多...
.NET开源、功能强大、跨平台的图表库LiveChart2

.NET开源、功能强大、跨平台的图表库LiveChart2

LiveCharts2 是 从LiveCharts演变而来，它修复了其前身的主要设计问题，它专注于在任何地方运行，提高了灵活性，并继承LiveCharts原有功能。 极其灵活的数据展示图库 （效果图） 开始使用 Live charts 是 .Net 的跨平台图表库，请访问 https://livecharts.dev 并查看目标平…
阅读更多...
Docker——目录迁移

Docker——目录迁移

我们在生产环境中安装Docker时&#xff0c;默认的安装目录是/var/lib/docker&#xff0c;而通常情况下&#xff0c;规划给系统盘的目录一般为50G&#xff0c;该目录是比较小的&#xff0c;一旦容器过多或容器日志过多&#xff0c;就可能出现Docker无法运行的情况&#xff0c;所…
阅读更多...
设计模式-迭代器模式

设计模式-迭代器模式

作者持续关注 WPS二次开发专题系列&#xff0c;持续为大家带来更多有价值的WPS开发技术细节&#xff0c;如果能够帮助到您&#xff0c;请帮忙来个一键三连&#xff0c;更多问题请联系我&#xff08;QQ:250325397&#xff09; 目录 定义 特点 使用场景 优缺点 (1) 优点 (2)…
阅读更多...
类与对象（二）

类与对象（二）

封装 封装作为面向对象三大特性&#xff08;封装&#xff0c;继承&#xff0c;多态&#xff09;之一&#xff0c;那如何实现封装性的呢&#xff1f;就又得拿出上面的访问修饰限定符的图 public: 就是在任何地方都可以访问 protected: 涉及子类在介绍继承时详细介绍 default: …
阅读更多...
LeetCode //C - 93. Restore IP Addresses

LeetCode //C - 93. Restore IP Addresses

93. Restore IP Addresses A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros. For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses, bu…
阅读更多...
Redis实战笔记

Redis实战笔记

黑马点评项目笔记 一&#xff1a;数据交互&#xff1a; 1.把String解析成Java对象集合并且存入Redis及Java对象集合转换成JSON。 Overridepublic Result queryTypeList() {String s stringRedisTemplate.opsForValue().get("cache:list:");System.out.println(&qu…
阅读更多...
Docker 部署 Nginx 实现一个极简的 负载均衡

Docker 部署 Nginx 实现一个极简的 负载均衡

背景: Nginx是异步框架的网页服务器&#xff0c;其常用作反向代理(负载均衡器)。在一般的小项目中, 服务器不多, 如果不考虑使用服务注册与发现, 使用Nginx 可以容易实现负载均衡。 在特此写一个快速入门 Nginx 的技术贴, 使用 Docker 部署 Nginx, 实现一个极简的加权轮询负载均…
阅读更多...
【go项目01_学习记录11】

【go项目01_学习记录11】

操作数据库 1 文章列表2 删除文章 1 文章列表 &#xff08;1&#xff09;先保证文章已经有多篇&#xff0c;可以直接在数据库中添加&#xff0c;或者访问链接: localhost:3000/articles/create&#xff0c;增加几篇文章。 &#xff08;2&#xff09;之前设置好了articles.ind…
阅读更多...
爬虫 Python将网页内容保存为PDF(url转pdf) 譬如下载某个专栏下的全部文章

爬虫 Python将网页内容保存为PDF(url转pdf) 譬如下载某个专栏下的全部文章

我看到一个不错的教程&#xff0c;想下载教程下全部文章到本地&#xff0c;有时间看看&#xff0c;但是问了作者没有电子档&#xff0c;就想办法了。 PS: 我一天天的到底在干嘛&#xff01;唉… 需求: 爬取一个网页里全部文章且存为pdf 参考链接: 【已解决】Python将网页内容…
阅读更多...
JS_监听dom变化触发，new MutationObserver

JS_监听dom变化触发，new MutationObserver

MutationObserver 是一个用于监测 DOM 变化的接口&#xff0c;它提供了一种机制来异步观察在特定元素或文档中发生的 DOM 变化。 MutationObserver 的作用包括&#xff1a; 1.监测 DOM 变化&#xff1a;你可以创建一个 MutationObserver 实例&#xff0c;并指定一个回调函数。…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站