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

【513. 找树左下角的值 中等】

题目:

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:
在这里插入图片描述
输入: root = [2,1,3]
输出: 1

示例 2:
在这里插入图片描述
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

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

思路:

  1. 递归法

    该题有一个容易迷惑的地方,就是最底层最左边的值并不一定是左叶子节点的值,比如输入:[1,null,1],那最底层最左边的值就是右叶子节点的值:1。

    所以递归的终止条件不能模仿 404. 左叶子之和中那样写,即不能写成下面这样:

    if(node->left && !node->left->left && !node->left->right){    //  到达左叶子节点,将值累加到resultresult = node->left->val;
    }
    

    这样会漏掉左叶子节点为空,而右叶子节点有值的情况。

    所以应该借助深度来写递归,即记录让深度值变大的第一个值,不论是左叶子节点,还是右叶子节点。最后一次记录的一定是最底层最左边的值。

    递归三部曲:

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

    参数必须有要遍历的树的根节点,还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了,所以递归函数的返回类型为void。

    本题还需要类里的两个全局变量,maxLen用来记录最大深度,result记录最大深度最左节点的数值。

    代码如下:

    int maxDepth = INT_MIN;   // 全局变量 记录最大深度
    int result;       // 全局变量 最大深度最左节点的数值
    void traversal(TreeNode* root, int depth)
    
  • 确定终止条件

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

    代码如下:

    if (root->left == NULL && root->right == NULL) {
    if (depth > maxDepth) {maxDepth = depth;           // 更新最大深度result = root->val;   // 最大深度最左面的数值
    }
    return;
    }
    
  • 确定单层递归的逻辑

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

    	                // 中
    if (root->left) {   // 左depth++; // 深度加一traversal(root->left, depth);depth--; // 回溯,深度减一
    }
    if (root->right) { // 右depth++; // 深度加一traversal(root->right, depth);depth--; // 回溯,深度减一
    }
    return;
    
  1. 迭代法

    本题使用层序遍历再合适不过了,比递归要好理解得多!

    只需要记录最后一行第一个节点的数值就可以了。


代码:

  1. 递归法
class Solution {
public:int maxDepth = INT_MIN; // 全局变量 记录最大深度int result; // 全局变量 最大深度最左节点的数值void traversal(TreeNode* root, int depth) {if (root->left == NULL && root->right == NULL) {if (depth > maxDepth) {maxDepth = depth;    // 更新最大深度result = root->val; // 最大深度最左面的数值}return;}if (root->left) {depth++;traversal(root->left, depth);depth--; // 回溯}if (root->right) {depth++;traversal(root->right, depth);depth--; // 回溯}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};
  1. 迭代法
class Solution {
public:int findBottomLeftValue(TreeNode* root) {//  if(root == NULL) return 0;int result = 0;queue<TreeNode*> que1;if(root != NULL) que1.push(root);while(!que1.empty()){int size = que1.size();for(int i = 0; i < size; i++){TreeNode* node = que1.front();que1.pop();if(i == 0) result = node->val;  //  到达左叶子节点就替换result的值,最后一次就是最底层,最左边节点的值if(node->left) que1.push(node->left);if(node->right) que1.push(node->right);}}return result;}
};

总结:

本题比较迷惑的点就是容易误认为最左边的值就是左叶子节点的值,而写错递归的终止条件。

递归法要注意回溯。


参考:

代码随想录

相关文章:

【513. 找树左下角的值 中等】

题目&#xff1a; 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 示例 2: 输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7 提示: 二叉树的节点个数的范围是 …...

网络通信的瑞士军刀:Python socket库全解析

文章目录 网络通信的瑞士军刀&#xff1a;Python socket库全解析背景库介绍安装与重要性简单库函数使用方法场景应用常见Bug及解决方案总结 网络通信的瑞士军刀&#xff1a;Python socket库全解析 背景 在现代编程中&#xff0c;网络通信是不可或缺的一部分。无论是构建客户端…...

【笔记️】魔爪 Mini mx 使用快捷键

B站教程地址&#xff1a;MOZA魔爪的个人空间-MOZA魔爪个人主页-哔哩哔哩视频 1、开关键: 单击 → 开启录制/拍照 → 再次单击结束&#xff1b;休眠时,单击晚醒 双击 → 切换拍照/录制模式 三击 → 切换横竖拍 长按 → 关机 2、变焦键: 单击 → 切换航向俯仰跟随模式 ( 开机默…...

去除 el-input 输入框的边框(element-ui@2.15.13)

dgqdgqdeMac-mini spid-admin % yarn list --pattern element-ui yarn list v1.22.22 └─ element-ui2.15.13 ✨ Done in 0.23s.dgqdgqdeMac-mini spid-admin % yarn list vue yarn list v1.22.22 warning Filtering by arguments is deprecated. Please use the pattern opt…...

Vue中的一些用法

一、验证规则&#xff1a; 身份证的验证规则&#xff1a; 电话号码的验证规则&#xff1a; 二、选中一项后禁用其他选项&#xff1a; data(){ return{ dataForm{ medicalHistory:[] } }, 三、多选框选择后页面中不显示数据&#xff1a; 在表单提交时加 .join(",&…...

异步爬虫之协程的基本原理

我们知道爬虫是 IO 密集型任务&#xff0c;例如使用 requests 库来爬取某个站点&#xff0c;当发出一个请求后&#xff0c;程序必须等待网站返回响应&#xff0c;才能接着运行&#xff0c;而在等待响应的过程中&#xff0c;整个爬虫程序是一直在等待的&#xff0c;实际上没有做…...

Diffusion Transformer(DiT)——将扩散过程中的U-Net换成ViT:近频繁用于视频生成与机器人动作预测(含清华PAD详解)

前言 本文最开始属于此文《视频生成Sora的全面解析&#xff1a;从AI绘画、ViT到ViViT、TECO、DiT、VDT、NaViT等》 但考虑到DiT除了广泛应用于视频生成领域中&#xff0c;在机器人动作预测也被运用的越来越多&#xff0c;加之DiT确实是一个比较大的创新&#xff0c;影响力大&…...

CPT203 Software Engineering 软件工程 Pt.2 敏捷方法和需求工程(中英双语)

文章目录 3. Aglie methods&#xff08;敏捷方法&#xff09;3.1 Aglie methods&#xff08;敏捷方法&#xff09;3.1.1 特点3.1.2 优点3.1.3 缺点3.1.4 原则3.1.5 计划驱动与敏捷方法的对比 3.2 Scrum3.2.1 Scrum roles3.2.2 Scrum Activities and Artifacts3.2.2.1 Product B…...

【Git】-- 在本地执行 git fetch 发生异常

目录 1、现象 2、解决参考 2.1 检查网络连接 2.2 更新 Git 客户端 2.3 更改 GitHub URL 的访问协议 2.4 禁用 SSL 验证&#xff08;临时解决&#xff09; 2.5 检查系统的 CA 证书 2.6 重新克隆仓库 1、现象 在本地执行 $ git fetch upstream 时&#xff0c;抛出以下…...

Apache Doris 创始人:何为“现代化”的数据仓库?

在 12 月 14 日的 Doris Summit Asia 2024 上&#xff0c;Apache Doris 创始人 & PMC 成员马如悦在开场演讲中&#xff0c;围绕“现代化数据仓库”这一主题&#xff0c;指出 3.0 版本是 Apache Doris 研发路程中的重要里程碑&#xff0c;他将这一进展总结为“实时之路”、“…...

高校网络安全存在的问题与对策研究

目 录 摘 要1 第1章 引言2 1.1研究背景2 1.2研究意义2 第2章系统开发的相关技术简介3 2.1 Spring boot框架3 2.2 MySQL简介3 2.3 Vue框架3 2.4 JAVA简介3 第3章 系统需求分析4 3.1可行性分析4 3.1.1技术可行性4 3.1.2运行可行性4 3.1.3经济可行性5 3.2功能需求…...

Redis的数据类型,线程,持久化机制

1. Redis是单线程还是多线程的&#xff0c;为什么&#xff1f; Redis是单线程的&#xff08;传统实现&#xff09; Redis在传统的实现中是单线程的。尽管它处理的任务很多&#xff0c;但它使用单线程来处理所有客户端的请求。这个设计决策有几个关键原因&#xff1a; 简化模型…...

什么是ondelete cascade以及使用sqlite演示ondelete cascade使用案例

什么是ondelete cascade ‌ON DELETE CASCADE是数据库中的一种约束&#xff0c;用于自动删除相关的记录‌。具体来说&#xff0c;当一个表中的记录&#xff08;父表&#xff09;被删除时&#xff0c;与其相关的其他表&#xff08;子表&#xff09;中的记录也会被自动删除&…...

Java设计模式 —— 【结构型模式】享元模式(Flyweight Pattern) 详解

文章目录 概述结构案例实现优缺点及使用场景 概述 享元模式也叫蝇量模式&#xff1a;运用共享技术有效地支持大量细粒度的对象&#xff1b; 常用于系统底层开发&#xff0c;解决系统的性能问题。像数据库连接池&#xff0c;里面都是创建好的连接对象&#xff0c;在这些连接对象…...

数据的简单处理——pandas模块——选择数据

要对读取的数据进行编辑&#xff0c;需要先学会选择数据的操作&#xff0c;如果选择行数据、列数据或者同时选择行列数据。 ############################## ##作者&#xff1a;白雪公主的后妈 ##时间&#xff1a;2024年12月29日 ##主题&#xff1a;数据的简单处理——pandas模…...

淘宝/天猫购物车商品列表API:深度解析与应用实践

引言 在电商领域&#xff0c;购物车功能是提升用户体验和增加销售额的关键工具。淘宝和天猫作为中国最大的电商平台&#xff0c;提供了丰富的API接口&#xff0c;其中包括获取购物车商品列表的API&#xff0c;即buyer_cart_list。本文将深入解析淘宝/天猫购物车商品列表API的功…...

位置式PID-控制步进电机-位置环-stm32

基本原理 1、软件设计 本闭环控制例程是在步进电机编码器测速例程的基础上编写的,这里只讲解核心的部分代码,有些变量的设置,头文件的包含等并没有涉及到,完整的代码请参考本章配套的工程。 我们创建了4个文件:bsp_pid.c和bsp_pid.h文件用来存放PID控制器相关程序,bsp_s…...

关于Qt::BlockingQueuedConnection的死锁问题

绑定信号槽时&#xff0c;如果信号对象和槽对象属于不同的线程&#xff0c;通过Qt::BlockingQueuedConnection可以实现同步调用&#xff0c;即发送信号的代码等待槽函数返回才继续运行 文档的说明&#xff1a; Qt::QueuedConnection The slot is invoked when control returns…...

Excel for Finance 07 `FV PV` 函数

Excel 的 FV 函数用于计算一笔投资在未来的价值&#xff0c;基于固定的利率和定期付款。这是一个金融函数&#xff0c;常用来分析储蓄计划、贷款、或投资的增长。 语法&#xff1a; FV(rate, nper, pmt, [pv], [type])参数说明&#xff1a; rate&#xff08;必需&#xff09;&…...

驱动开发系列31 - Linux Graphics 调试 mesa 的 glDrawArrays (三)

一:概述 接着前面驱动开发系列26 - Linux Graphics 调试 mesa 的 glDrawArrays (二)-CSDN博客的文章继续分析下glDrawArrays的实现,本文介绍一下在Gallium3D HW Driver中,驱动如何将绘制命令提交给GPU执行。看下驱动层的执行逻辑:即 draw_vbo 的过程。 二:回顾下draw_vbo…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...