【LeetCode】升级打怪之路 Day 21:二叉树的最近公共祖先(LCA)问题

news/2024/5/29 5:27:12/文章来源:https://blog.csdn.net/qq_45668004/article/details/136679662

今日题目:

  • 236. 二叉树的最近公共祖先
  • 1644. 二叉树的最近公共祖先 II
  • 235. 二叉搜索树的最近公共祖先

目录

    • LCA 问题
      • LC 236. 二叉树的最近公共祖先 【classic】
      • LC 1644. 二叉树的最近公共祖先 II 【稍有难度】
      • LC 235. 二叉搜索树的最近公共祖先 ⭐⭐⭐

今天做了几道有关二叉树的最近公关祖先(LCA)问题,没有接触过的话,直接上手就能解答出来还是存在不少困难的。今天学习了相关的解题思路,寻找 LCA 问题的框架在本质上还是一个二叉树递归遍历的框架。重点需要把握好代码实现中辅助函数 find() 的语义,以及为什么这样实现。根据 LCA 可能出现的情况,实现 LCA 的寻找

LCA 问题

最近公共祖先(Lowest Common Ancestor,LCA)问题是一类问题,这类题目也存在一定的难度,因此需要认真学习一下。

labuladong 的 Git原理之最近公共祖先 这篇文章介绍了 LCA 问题的解题思路,可以参考学习一下。

LC 236. 二叉树的最近公共祖先 【classic】

236. 二叉树的最近公共祖先

这个题目就是经典的 LCA 问题。

我们想要找 p 和 q 的 LCA,那这个 LCA 有两种情况:

  • case 1:自己是 p 或 q,另一个在自己的子树上(或者也还是自己)
  • case 2:自己不是 p 或 q,其中一个在自己左子树上,另一个在自己右子树上

对于寻找 LCA 的问题,我们可以写一个 find() 辅助函数来完成递归寻找。

我们需要明确一下 find() 函数的语义:它从 root 开始寻找它认为最可能是 LCA 的节点。这里限定是“最可能”是因为,在 case 1 中,如果一个节点发现自己是 p 或 q,那它就不需要再向下找了,因为从自己这个层次上来看, 如果有 LCA 的话,那也只能是自己,不可能是再向下的子树中的节点了。至于真的是不是 LCA,就交由更上层的节点来验证,如果更上层的节点没有再找到另一个 p 或 q,那就是了。所以 find 函数只需要返回当前这个节点自认为最可能是 LCA 的节点就可以。来看代码:

236 题目

可以看到,find() 函数就是返回一个节点在自己层级上所认为的最可能是 LCA 的节点。因为题目说了一定存在 p 和 q,也就是一定存在 LCA,所以最终返回的就是 root 所认为的最可能是 LCA 的节点,它是一定存在的。

LC 1644. 二叉树的最近公共祖先 II 【稍有难度】

1644. 二叉树的最近公共祖先 II

这个题目相比于上个题目有了变动,上一个题目明确说了一定存在 LCA,但这个题目却不一定,所以在这题目中,我们无法肯定 find() 函数返回的最终结果就是 LCA,需要加一个标志位用来区分是否真的找到了 LCA。

在之前的 find() 函数的逻辑中,当一个节点自己就等于 p 或 q 之一时就返回自己作为可能的 LCA,没有再向下确定自己的子树中是否还存在另一个目标值,从而导致了这种不确定性。因为我们的遍历本质上是后序递归遍历,所以遍历一定是遍历了所有节点,也就是如果存在 p 或 q,我们是一定能遍历到的,所以我们可以加一个标志位来记录是否找到了 p 和 q。如果最终标志位说明找到了 p 和 q,那 find() 函数返回的 TreeNode 就是我们要找的 LCA 节点了。

所以这个题目的解法相比于上个题目,主要是加了个标志位:

1644
可以看到,代码整体思路与之前的一样,只是加了个标志位,用来判断最终找到的结果是不是 LCA。

LC 235. 二叉搜索树的最近公共祖先 ⭐⭐⭐

235. 二叉搜索树的最近公共祖先

这个题目也是个变形。将二叉树改为二叉搜索树,需要利用上 BST 的相关特性。

其实只当它是个二叉树的话,之前的题目的解法也能做这个题目,这个题目的难点在于如何利用上 BST 的特性。

因为我们的 find() 本质上还是递归遍历寻找目标值,如果是在 BST 上进行遍历的话,我们可以利用目标值的大小和当前值的大小进行对比,从而避免向不可能存在目标值的分支上进行查找。

为了实现“剪枝”的效果,我们这一次 find() 函数的实现中,将判断是否自己是 LCA 逻辑放到了递归之前,也就是前序的位置,这样的话,如果根据某些条件来决定出哪个子树不需要递归下去了。

代码思路及实现如下:

235 代码

做了这个题,我们就可以对寻找 LCA 问题有了更深的理解。

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

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

相关文章

使用电脑的时候最怕有英文?微信的这个功能一定要用起来!

相信各位小伙伴对微信都不陌生。我们平常使用微信的大部分时间都是聊天、朋友圈、视频号等。 如果有人给你发来一张全英文图片的截图,你会咋整? 请人翻译?这个显然不需要。 一个个字母手打上去?这字数少了还行,但多了…

基于Java的开放实验室管理系统(Vue.js+SpringBoot)

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、研究内容2.1 实验室类型模块2.2 实验室模块2.3 实验管理模块2.4 实验设备模块2.5 实验订单模块 三、系统设计3.1 用例设计3.2 数据库设计 四、系统展示五、样例代码5.1 查询实验室设备5.2 实验放号5.3 实验预定 六、免责说明 一、摘…

设计模式学习笔记 - 设计原则 - 10.实战:针对非业务的通用框架开发,如何做需求分析和设计及如何实现一个支持各种统计规则的性能计数器

前言 接下来我们在结合一个支持各种统计规则的性能计数项目,学习针对一个非业务的通用框架开发,如何来做需求分析、设计和实现,同时学习如何灵活应用各种设计原则。 项目背景 设计开发一个小的框架,能够获取接口调用的各种统计信…

每日学习笔记:C++ 11的Tuple

#include <tuple> Tuple介绍(不定数的值组--可理解为pair的升级版) 定义 创建 取值 初始化 获取tuple元素个数、获取tuple某元素类型、将2个tuple类型串接为1个新tuple类型

基于Python的中医药知识问答系统设计与实现

[简介] 这篇文章主要介绍了基于Python的中医药知识问答系统的设计与实现。该系统利用Python编程语言&#xff0c;结合中医药领域的知识和技术&#xff0c;实现了一个功能强大的问答系统。文章首先介绍了中医药知识的特点和传统问答系统的局限性&#xff0c;然后提出了设计思路…

python INI文件操作与configparser内置库

目录 INI文件 configparser内置库 类与方法 操作实例 导入INI文件 查询所有节的列表 判断某个节是否存在 查询某个节的所有键的列表 判断节下是否存在某个键 增加节点 删除节点 增加节点的键 修改键值 保存修改结果 获取键值 获取节点所有键值 其他读取方式 …

54、WEB攻防——通用漏洞跨域CORS资源JSONP回调域名接管劫持

文章目录 同源策略CORSJSONP跨域回调子域名劫持 同源策略 同源策略包括三个条件&#xff1a;同域名、同域名、同端口。同源策略限制从一个源加载的文档或脚本与来自另一个源的资源进行交互。 CORS CORS&#xff08;跨域资源共享&#xff09;已被所有浏览器支持&#xff0c;跨…

leetcode代码记录(有效的括号

目录 1. 题目&#xff1a;2. 我的代码&#xff1a;小结&#xff1a; 1. 题目&#xff1a; 给定一个只包括 ‘(’&#xff0c;‘)’&#xff0c;‘{’&#xff0c;‘}’&#xff0c;‘[’&#xff0c;‘]’ 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&…

缩写

解法&#xff1a; 看字符串首元素即可 #include<iostream> #include<vector> #include<string> #include<sstream> using namespace std; #define endl \n void solve() {cin >> ws;string s, str;getline(cin, s);stringstream ss(s);while (…

【wine】WINEDEBUG 分析mame模拟器不能加载roms下面的游戏 可以调整参数,快速启动其中一个游戏kof98

故障现象&#xff0c;MAME启动后&#xff0c;游戏都没有识别 添加日志输出&#xff0c;重新启动wine #!/bin/bashexport WINEPREFIX$(pwd)/.wine export WINESERVER$(pwd)/bin/wineserver export WINELOADER$(pwd)/bin/wine export WINEDEBUG"file,mame,warn,err"…

《计算机网络》:考研 2024/3/5 2.1.1-物理层基本概念引入

2024/3/5 2.1.1 物理层基本概念 Ch1. 本章思维导图 图1. 物理层思维导图 Ch2. 物理层接口特性 所谓物理层&#xff0c;物理层解决如何在连接各种计算机的传输媒体上传输数据比特流&#xff0c;而不是指具体的传输媒体。物理层的主要任务&#xff1a;确定与传输媒体接口有关…

面试经典150题——两数相加

​Anything is worth "fighting for," and when you get it, dont doubt it, you deserve it, you deserve it. 1. 题目描述 2. 题目分析与解析 2.1 思路一 这个题目虽然标的是中等&#xff0c;但是大家看一下应该还是比较容易想到思路的&#xff0c;这不就相当于…

Keepalived+LVS构建高可用集群

目录 一、Keepalive基础介绍 1. Keepalive与VRRP 2. VRRP相关技术 3. 工作原理 4. 模块 5. 架构 6. 安装 7. Keepalived 相关文件 7.1 配置组成 7.2 全局配置 7.3 VRRP实例配置&#xff08;lvs调度器&#xff09; 7.4 虚拟服务器与真实服务器配置 二、Keepalived…

mac系统下GCC优化编译的使用

mac系统下GCC优化编译的使用 编译流程 预处理&#xff1a;g -E homework.cpp -o homework.i 编译&#xff1a;g -S homework.i -o homework.s //.s为汇编文件 汇编&#xff1a;g -c homework.s -o homework.o 链接&#xff1a;g homework.o -o homework 优化选项 -O0&#…

前端网页如何在 Windows 上测试 Safari

“Windows上的Safari&#xff1f;”&#xff0c;“那不可能&#xff01; Safari 无法在 Windows 上运行。当然的&#xff01; 曾经可以在windows上运行&#xff0c;但苹果早在 2012 年就停止支持 Windows。对于想要测试 Safari 兼容性的 Web 开发人员来说&#xff0c;这真是太不…

数据结构-树状数组

&#x1f4d1;前言 本文主要是【树状数组】——树状数组简单使用的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他 &#x1f304;每日一…

VR数字展厅在企业中应用的优势有哪些?

随着VR全景技术的成熟&#xff0c;VR数字展厅逐渐成为了企业展示形象和产品的重要手段之一。VR企业数字展厅是一种通过VR技术、3D建模技术展示企业形象和产品的创新方式&#xff0c;将企业线下的展厅搬到线上&#xff0c;为企业品牌形象带来了很多优势。 VR数字展厅在企业中应用…

【大厂AI课学习笔记NO.68】开源和开源发展情况

开源即源代码公开&#xff0c;任何人能获取源代码&#xff0c;查看、修改、分发他们认为合适的代码。 依托同行评审和社区生成&#xff0c;旨在以分散、协作的方式开发。 我们曾经很详细的讨论过开源协议的问题&#xff0c;详细可以参考我的文章&#xff1a; https://giszz.…

为什么要用scrapy爬虫库?而不是纯python进行爬虫?

为什么要用scrapy爬虫库&#xff1f;而不是纯python进行爬虫&#xff1f; Scrapy的优点Scrapy节省的工作使用纯Python编写爬虫的不足 Scrapy是一个使用Python编写的开源和协作的web爬虫框架&#xff0c;它被设计用于爬取网页数据并从中提取结构化数据。Scrapy的强大之处在于其广…

新手如何快速上手学习单片机?

读者朋友能容我&#xff0c;不使博文负真心 新开专栏&#xff0c;期待与诸君共享精彩 个人主页&#xff1a;17_Kevin-CSDN博客 专栏&#xff1a;《单片机》 学习单片机是一个有趣且有挑战性的过程。单片机是一种微控制器&#xff0c;广泛应用于各种电子设备和嵌入式系统中。在这…