513. 找树左下角的值 - 力扣(LeetCode)

题目描述

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

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

题目示例

在这里插入图片描述

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

解题思路

深度优先搜索
使用 depth 记录遍历到的节点的深度,result 记录深度在 depth 的最左节点的值。在深度优先搜索时,我们先搜索当前节点的左子节点,再搜索当前节点的右子节点,然后判断当前节点的深度 depth 是否大于 maxDepth,如果是,那么将 result 设置为当前结点的值,maxDepth 设置为 depth。

由于我们总是先遍历左节点,再遍历右节点,所以我们可以保证我们每一次更新的最大深度时总是在当前层中的最左侧,记录的是最大深度最左侧节点的值。

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

参考代码

深度优先搜索

class Solution {public int maxDepth = Integer.MIN_VALUE;public int result;public int findBottomLeftValue(TreeNode root) {traversal(root, 0);return result;}public void traversal(TreeNode node, int depth) {// 如果是叶子结点if(node.left == null && node.right == null) {// 因为每一层是先看左再看右,所以第一个是最左边的// 判断是不是第一个遇到的叶子结点,代表是最左边的if(depth > maxDepth) {maxDepth = depth;result = node.val;return;}}if(node.left != null) {traversal(node.left, depth + 1);}if(node.right != null) {traversal(node.right, depth + 1);}}
}

广度优先搜索

class Solution {public int findBottomLeftValue(TreeNode root) {int ret = 0;Queue<TreeNode> queue = new ArrayDeque<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {TreeNode p = queue.poll();if (p.right != null) {queue.offer(p.right);}if (p.left != null) {queue.offer(p.left);}ret = p.val;}return ret;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/253865.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

幻兽帕鲁mac可以玩吗?

《幻兽帕鲁》&#xff08;英文&#xff1a;Palworld&#xff09;是一款近期在 Steam 爆红的动作冒险生存游戏&#xff0c;游戏设置在一个居住着「帕鲁」的开放世界中&#xff0c;玩家可以战斗并捕捉帕鲁&#xff0c;也能用它们来建造基地、骑乘和战斗。 不过目前《幻兽帕鲁》仅…

Appium使用初体验之参数配置,简单能够运行起来

一、服务器配置 Appium Server配置与Appium Server GUI&#xff08;可视化客户端&#xff09;中的配置对应&#xff0c;尤其是二者如果不在同一台机器上&#xff0c;那么就需要配置Appium Server GUI所在机器的IP&#xff08;Appium Server GUI的HOST也需要配置本机IP&#xf…

Android Studio安装过程遇到SDK无法安装问题解决

首次打开studio遇到该类问题&#xff0c;需要下载SDK文件&#xff0c;后又发现SDK由于是Google源&#xff0c;无法进行正常安装&#xff0c;故转而进行SDK的镜像安装。 一、下载SDK Tools 地址&#xff1a;AndroidDevTools - Android开发工具 Android SDK下载 Android Studio…

macbook电脑如何永久删除app软件?

在使用MacBook的过程中&#xff0c;我们经常会下载各种App来满足日常的工作和娱乐需求。然而&#xff0c;随着时间的积累&#xff0c;这些App不仅占据了宝贵的硬盘空间&#xff0c;还可能拖慢电脑的运行速度。那么&#xff0c;如何有效地管理和删除这些不再需要的App呢&#xf…

C++面试宝典第27题:完全平方数之和

题目 给定正整数 n,找到若干个完全平方数(比如:1、4、9、16、...),使得它们的和等于n。你需要让组成和的完全平方数的个数最少。 示例1: 输入:n = 12 输出:3 解释:12 = 4 + 4 + 4。 示例2: 输入:n = 13 输出:2 解释:13 = 4 + 9。 解析 这道题主要考察应聘者对于…

JVM-运行时数据区程序计数器

运行时数据区 Java虚拟机在运行Java程序过程中管理的内存区域&#xff0c;称之为运行时数据区。《Java虚拟机规范》中规定了每一部分的作用。 程序计数器的定义 程序计数器&#xff08;Program Counter Register&#xff09;也叫PC寄存器&#xff0c;每个线程会通过程序计数器…

SpringCloud-Eureka原理分析

Eureka是Netflix开源的一款用于实现服务注册与发现的工具。在微服务架构中&#xff0c;服务的动态注册和发现是必不可少的组成部分&#xff0c;而Eureka正是为了解决这一问题而诞生的。 一、为何需要Eureka 在微服务架构中&#xff0c;服务之间的协同合作和高效通信是至关重要…

网络原理TCP/IP(1)

文章目录 端口号UDP协议 在网络通信中&#xff0c;协议非常重要 协议进行了分层 应用层就是对应着应用程序&#xff0c;是程序员打交道最多的这一层&#xff0c;调用系统提供的网络api写出来的代码都是属于应用层的 应用层有很多现成的协议&#xff0c;但是更多的还是程序员需要…

Redis篇之集群

一、主从复制 1.实现主从作用 单节点Redis的并发能力是有上限的&#xff0c;要进一步提高Redis的并发能力&#xff0c;就需要搭建主从集群&#xff0c;实现读写分离。主节点用来写的操作&#xff0c;从节点用来读操作&#xff0c;并且主节点发生写操作后&#xff0c;会把数据同…

RabbitMQ详解

RabbitMQ 1.初识MQ 1.1.同步和异步通讯 微服务间通讯有同步和异步两种方式&#xff1a; 同步通讯&#xff1a;就像打电话&#xff0c;需要实时响应。 异步通讯&#xff1a;就像发邮件&#xff0c;不需要马上回复。 两种方式各有优劣&#xff0c;打电话可以立即得到响应&a…

设计模式理解:单例模式+工厂模式+建设者模式+原型模式

迪米特法则&#xff1a;Law of Demeter, LoD, 最少知识原则LKP 如果两个软件实体无须直接通信&#xff0c;那么就不应当发生直接的相互调用&#xff0c;可以通过第三方转发该调用。其目的是降低类之间的耦合度&#xff0c;提高模块的相对独立性。 所以&#xff0c;在运用迪米特…

一文读懂转融通

最近多家公司都在讲解关于转融通要求。今天我们就来详细聊聊&#xff01; 转融通是一种证券借贷机制&#xff0c;它允许机构投资者在融资融券交易中借入或借出证券。 具体来说&#xff0c;机构投资者可以向券商借入证券&#xff0c;或者将持有的证券借给券商&#xff0c;以扩大…

诺奖经济学家称AI将取代STEM专业工作!Altman:人类无需工作,我给发钱

最近&#xff0c;2010年诺贝尔经济学奖得主&#xff0c;伦敦政治经济学院&#xff08;LSE&#xff09;教授Christopher Pissarides公开表态&#xff0c;在不远的未来&#xff0c;传统意义上的「数理化」学科知识和技能&#xff0c;都将会被AI取代。 这位劳动力市场经济学家警告…

mac检查CPU温度和风扇速度软件:Macs Fan Control Pro 1.5.17中文版

Macs Fan Control Pro for Mac是一款专业的电脑风扇控制工具&#xff0c;旨在帮助Mac用户有效控制电脑的风扇速度&#xff0c;提高电脑的运行效率和稳定性。 软件下载&#xff1a;Macs Fan Control Pro 1.5.17中文版 该软件支持多种风扇控制模式和预设方案&#xff0c;用户可以…

Vue源码系列讲解——虚拟DOM篇【一】(Vue中的虚拟DOM)

目录 1. 前言 2. 虚拟DOM简介 2.1什么是虚拟DOM&#xff1f; 2.2为什么要有虚拟DOM&#xff1f; 3. Vue中的虚拟DOM 3.1 VNode类 3.2 VNode的类型 3.2.1 注释节点 3.2.2 文本节点 3.2.3 克隆节点 3.2.4 元素节点 3.2.5 组件节点 3.2.6 函数式组件节点 3.2.7 小结 3…

使用pygame生成红包封面

import pygame import sys# 初始化pygame pygame.init()# 设置红包封面尺寸 size width, height 640, 960 screen_color (255, 0, 0) # 红色背景# 创建窗口 screen pygame.display.set_mode(size) pygame.display.set_caption(红包封面)# 加载龙形图片 dragon_image pygam…

运维自动化bingo前端

项目目录结构介绍 项目创建完成之后&#xff0c;我们会看到bingo_web项目其实是一个文件夹&#xff0c;我们进入到文件夹内部就会发现一些目录和文件&#xff0c;我们简单回顾一下里面的部分核心目录与文件。 ├─node_modules/ # node的包目录&#xff0c;项目运行的依赖包…

【C++】模板入门教程

C模板是C编程中的重要利器&#xff0c;能够大大提高编码效率。函数模板和类模板是模板编程中的两个重要概念&#xff0c;它们允许我们编写独立于数据类型的通用代码。 本文将深入介绍函数模板和类模板的使用方法&#xff0c;以及它们的实现原理、匹配规则和注意事项&#xff0…

Python进阶--下载想要的格言(基于格言网的Python爬虫程序)

注&#xff1a;由于上篇帖子&#xff08;Python进阶--爬取下载人生格言(基于格言网的Python3爬虫)-CSDN博客&#xff09;篇幅长度的限制&#xff0c;此篇帖子对上篇做一个拓展延伸。 目录 一、爬取格言网中想要内容的url 1、找到想要的内容 2、抓包分析&#xff0c;找到想…

交友系统---让陌生人变成熟悉人的过程。APP小程序H5三端源码交付,支持二开。

随着社交网络的发展和普及&#xff0c;人们之间的社交模式正在发生着深刻的变革。传统的线下交友方式已经逐渐被线上交友取而代之。而同城交友正是这一趋势的产物&#xff0c;它利用移动互联网的便利性&#xff0c;将同城内的人们连接在一起&#xff0c;打破了时空的限制&#…