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

LeetCode 1123. 最深叶节点的最近公共祖先:DFS

【LetMeFly】1123.最深叶节点的最近公共祖先

力扣题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/

给你一个有根节点 root 的二叉树,返回它 最深的叶节点的最近公共祖先 。

回想一下:

  • 叶节点 是二叉树中没有子节点的节点
  • 树的根节点的 深度 为 0,如果某一节点的深度为 d,那它的子节点的深度就是 d+1
  • 如果我们假定 A 是一组节点 S 的 最近公共祖先S 中的每个节点都在以 A 为根节点的子树中,且 A 的深度达到此条件下可能的最大值。

 

示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4]
输出:[2,7,4]
解释:我们返回值为 2 的节点,在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意,节点 6、0 和 8 也是叶节点,但是它们的深度是 2 ,而节点 7 和 4 的深度是 3 。

示例 2:

输入:root = [1]
输出:[1]
解释:根节点是树中最深的节点,它是它本身的最近公共祖先。

示例 3:

输入:root = [0,1,3,null,2]
输出:[2]
解释:树中最深的叶节点是 2 ,最近公共祖先是它自己。

 

提示:

  • 树中的节点数将在 [1, 1000] 的范围内。
  • 0 <= Node.val <= 1000
  • 每个节点的值都是 独一无二 的。

 

注意:本题与力扣 865 重复:https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/

方法一:深度优先搜索(DFS)

们把最深的叶节点的最近公共祖先,称之为 lca \textit{lca} lca节点。

编写一个函数dfs(root),返回以root为根的子树的{lca, 深度}

  • 如果左子树更深,则返回{左子的lac, 左子深度 + 1}

  • 如果右子树更深,则返回{右子的lac, 右子深度 + 1}

  • 否则(左右子树深度相同),则返回{root,左子深度 + 1}

  • 时间复杂度 O ( n ) O(n) O(n),其中 n n n为二叉树节点个数

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

AC代码

C++

typedef pair<TreeNode*, int> pti;
class Solution {
private:pti dfs(TreeNode* root) {if (!root) {return {nullptr, 0};}pti left = dfs(root->left);pti right = dfs(root->right);if (left.second == right.second) {return {root, left.second + 1};}else if (left.second < right.second) {return {right.first, right.second + 1};}else {return {left.first, left.second + 1};}}
public:TreeNode* lcaDeepestLeaves(TreeNode* root) {return dfs(root).first;}
};

Python

# from typing import Optional# # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution:def dfs(self, root: Optional[TreeNode]):if not root:return [None, 0]left = self.dfs(root.left)right = self.dfs(root.right)if left[1] == right[1]:return [root, left[1] + 1]elif left[1] < right[1]:return [right[0], right[1] + 1]else:return [left[0], left[1] + 1]def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:return self.dfs(root)[0]

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/132725441

相关文章:

LeetCode 1123. 最深叶节点的最近公共祖先:DFS

【LetMeFly】1123.最深叶节点的最近公共祖先 力扣题目链接&#xff1a;https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/ 给你一个有根节点 root 的二叉树&#xff0c;返回它 最深的叶节点的最近公共祖先 。 回想一下&#xff1a; 叶节点 是二叉树…...

多线程应用——线程池

线程池 文章目录 线程池1.什么是线程池2.为什么要用线程池3.怎么使用线程池4.工厂模式5.自己实现一个线程池6.创建系统自带的线程池6.1 拒绝策略6.2 线程池的工作流程 1.什么是线程池 字面意思&#xff0c;一次创建多个线程&#xff0c;放在一个池子(集合类)&#xff0c;用的时…...

OPENCV+QT环境配置

【qtopencv开发入门&#xff1a;4步搞定opencv环境配置2】https://www.bilibili.com/video/BV1f34y1v7t8?vd_source0aeb782d0b9c2e6b0e0cdea3e2121eba 第一步&#xff1a; 安装QT Qt 5.15 第二步&#xff1a; 安装OPENCV VS2022 Opencv4.5.5 C 配置_愿飞翔的鱼儿的博客…...

Kafka3.0.0版本——文件清理策略

目录 一、文件清理策略1.1、文件清理策略的概述1.2、文件清理策略的官方文档1.3、日志超过了设置的时间如何处理1.3.1、delete日志删除&#xff08;将过期数据删除&#xff09;1.3.2、compact日志压缩 一、文件清理策略 1.1、文件清理策略的概述 Kafka 中默认的日志保存时间为…...

SRT参数说明

1.超时选项 connect_timeout 连接超时时间&#xff0c;单位毫秒&#xff0c;默认值为3秒。 当RTT > 1500毫秒(2次握手交换)时&#xff0c;SRT无法连接。此选项适用于caller和rendezvous模式。 listen_timeout 监听超时时间&#xff0c;单位毫秒 timeout 为读、写和连接操作…...

vue响应式原理

vue响应式原理 vue响应式原理vue2响应式原理目标对象为数组时 vue3响应式原理Vue3和Vue2在响应式系统方面的对比数据劫持的方式支持数据劫持的数据类型Vue3响应式系统显著优点是&#xff1a; vue响应式原理 无论vue2和vue3响应式都是通过观察者模式&#xff08;发布订阅模式&a…...

elk安装篇之 Kibana安装

Kibana是一个开源的分析与可视化平台&#xff0c;设计出来用于和Elasticsearch一起使用的。你可以用kibana搜索、查看存放在Elasticsearch中的数据。是es的可视化客户端之一。 一&#xff1a;下载 https://www.elastic.co/cn/kibana 我的es是elasticsearch-7.10.2版本&#x…...

MySQL 用户授权管理及白名单

1.创建用户 在 MySQL 中&#xff0c;你可以通过以下步骤创建用户并设置白名单&#xff1a; 使用管理员账号连接到 MySQL 服务器。 创建新用户&#xff1a; CREATE USER usernamehostname IDENTIFIED BY password;其中&#xff0c; username 是你要创建的用户名&#xff1b;ho…...

pc-签字画板vue-esign的使用

使用的是vue-esign组件 npm install vue-esign 首先下载组件在main.js中引入vue-esign&#xff0c;并且挂载 import { createApp } from vue; import App from ./App.vue; const app createApp(App);import vueEsign from vue-esign app.use(vueEsign ) 页面使用&#xff0…...

javaScript:节点操作

目录 前言 常用的节点操作 innerHTML 的两个弊端&#xff08;补充&#xff09; createElement(标签名)使用dom方法创建一个元素 父元素.appendChild(子元素) 添加到父元素 注意 指定插入 父元素.insertBefore(要添加的元素&#xff0c;父元素中的指定子元素) 注意&…...

git 忽略已经提交的文件或文件夹 (修改.gitignore文件无效)

场景描述&#xff1a;项目开发到一半&#xff0c;追加了模块&#xff0c;提交的时候未注意将不需要提交的文件或者目录提交到.gitignore&#xff0c;然后提交后发现再修改git配置文件已无法阻拦更新&#xff0c;查阅官方资料&#xff1a; 核心点&#xff1a;.gitignore 之前&a…...

学习左耳听风栏目90天——第十二天 12/90(学习左耳朵耗子的工匠精神,对技术的热爱)【时间管理:同扭曲时间的事儿抗争】

时间管理&#xff1a;同扭曲时间的事儿抗争 要学会说不...

前端如何将后台数组进行等分切割

前端如何切割数组 目标&#xff1a;前端需要做轮播&#xff0c;一屏展示12个&#xff0c;后端返回的数组需要进行切割&#xff0c;将数据以12为一组进行分割 环境&#xff1a;vue3tselement plus 代码如下&#xff1a; function divideArrayIntoEqualParts(array, chunkSiz…...

如何有效防止服务器被攻击?

随着互联网的快速发展&#xff0c;服务器安全问题日益引起人们的关注。近期&#xff0c;全球范围内频繁发生的服务器攻击事件引发了广泛关注。为了保护企业和个人的数据安全&#xff0c;有效防止服务器被攻击已成为迫在眉睫的任务。 首先&#xff0c;及时更新服务器的操作系统和…...

layui表格高度

layui表格的高度设置时使用 height:‘full’ 高度就是表格每个页面的总高度。也可以直接写数值&#xff0c;但是这是定高。 也可以使用 height&#xff1a;“full-数值”&#xff0c;比如 height:full-80 那么就会在表格占据剩余div的时候底部留100px。相当于margin-bottom:10…...

一文1800字从0到1使用Python Flask实战构建Web应用

Python Flask是一个轻量级的Web框架&#xff0c;它简单易用、灵活性高&#xff0c;适用于构建各种规模的Web应用。本文将介绍如何使用Python Flask框架来实战构建一个简单的Web应用&#xff0c;并展示其基本功能和特性。 第一部分&#xff1a;搭建开发环境 在开始之前我们需要…...

【LeetCode-中等题】210. 课程表 II

文章目录 题目方法一&#xff1a;bfs方法二&#xff1a;dfs 题目 这一题是在207题的基础上&#xff0c;要统计拓扑排序的顺序集合&#xff0c;所以只需要在207的基础上加入一个将拓扑排序的节点输出即可&#xff08;有环无拓扑排序&#xff09; 【LeetCode-中等题】207. 课程表…...

vue修饰符的用法

Vue修饰符是指在Vue模板中用于改变指令行为的特殊后缀。修饰符以.开头&#xff0c;用于指示指令应该如何绑定或响应事件。Vue修饰符在一些常见的指令中使用&#xff0c;例如v-on和v-model。常见的Vue修饰符包括&#xff1a; .prevent&#xff1a;阻止默认事件的发生。.stop&am…...

汽车3D HMI图形引擎选择

2002年,电影《少数派报告》让观众深入了解未来。 除了情节的核心道德困境之外,大多数人都对它的技术着迷。 我们看到了自动驾驶汽车、个性化广告和用户可以无缝交互的 3D 计算机界面。 令人惊讶的是,虽然故事发生在 2054 年,但许多科幻想象的作品已经成为现实。 对于汽车和…...

stable diffusion实践操作-webUI教程-不是基础-是特例妙用

系列文章目录 stable diffusion实践操作 提示&#xff1a;写完文章后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 系列文章目录前言一、SD webUI是什么&#xff1f;二、详细教程1. 相关插件安装1.1. 提示词插件安装和使用1.2 tagg标签妙用…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

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

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

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...