【数据结构】二叉树篇|超清晰图解和详解:二叉树的最近公共祖先

在这里插入图片描述

  • 博主简介:努力学习的22级计算机科学与技术本科生一枚🌸
  • 博主主页: @是瑶瑶子啦
  • 每日一言🌼: 你不能要求一片海洋,没有风暴,那不是海洋,是泥塘——毕淑敏

目录

  • 一、题目
  • 二、题解
  • 三、代码

一、题目

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

在这里插入图片描述

二、题解

在这里插入图片描述注意:祖先是包括自身的!

  • 🍊首先要明白,当root为p,q的最近祖先节点,只有下面3种情况:

    1. p,q在root分别存在于root的左右子树中(异侧)——>root即为最近祖先节点
    2. p, q均在root的左侧——>p/q即为最近祖先节点
    3. p, q均在root的右侧——>同理
    在这里插入图片描述

  • 🍊递归函数的定义public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)在以root为根节点的树中找并且返回p和q的最近的祖先节点。
    1.终止条件:

    • root == null;return null
    • root = = p 或者root = = q,直接返回p/q

    2.递推工作:(到这里说明此时p和q要么在此次递归的root的同侧或者异侧)left 用于记录在左侧进行寻找公共祖先(这里的递归函数作用就是单纯找q/p节点并且找到就返回的作用了,当然你可以另外写一个找节点的函数,但是没必要,因为定义的递归函数本身就能实现这个功能),right同理

  1. left和right均为null,说明root的左右都没有p,q,那就不存在公共节点,返回Null(有点扯,按理来说,p,q肯定是存在的,但是特判一下也不亏)

  2. left和right均不空,说明在此时递归情况是:p,q在root异侧,那么直接返回root即可
    在这里插入图片描述

    3. ⭐left不为空,right为空;right不为空,left为空。直接将不为空的那个返回即可!此时不为空的left/right指向的就是最近祖先节点。 在这里插入图片描述

三、代码

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q){return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left != null && right !=null){return root;}else if(left == null){return right;}else if(right == null){return left;}else{return null;}}

💐若有不懂的地方,欢迎随时在评论区or私信找瑶瑶子交流讨论🌺

在这里插入图片描述

  • Java岛冒险记【从小白到大佬之路】

  • LeetCode每日一题–进击大厂

  • Go语言核心编程

  • 算法

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

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

相关文章

【宝藏系列】一文讲透C语言数组与指针的关系

【宝藏系列】嵌入式 C 语言代码优化技巧【超详细版】 文章目录 【宝藏系列】嵌入式 C 语言代码优化技巧【超详细版】👨‍🏫前言1️⃣指针1️⃣1️⃣指针的操作1️⃣2️⃣关于指针定义的争议1️⃣3️⃣对教材错误写法的小看法 2️⃣指针和数组的区别2️⃣…

内网穿透——使用Windows自带的网站程序建立网站

文章目录 1.前言2.Windows网页设置2.1 Windows IIS功能设置2.2 IIS网页访问测试 3. Cpolar内网穿透3.1 下载安装Cpolar3.2 Cpolar云端设置3.3 Cpolar本地设置 4.公网访问测试5.结语 1.前言 在网上各种教程和介绍中,搭建网页都会借助各种软件的帮助,比如…

java 使用log4j显示到界面和文件 并格式化

1.下载log4j jar包https://dlcdn.apache.org/logging/log4j/2.20.0/apache-log4j-2.20.0-bin.zip 2. 我只要到核心包 ,看需要 sources是源码包,可以看到说明。在IDEA里先加入class jar后,再双击这个class jar包或或右键选Navigate ,Add ,…

Xxl-job安装部署以及SpringBoot集成Xxl-job使用

1、安装Xxl-job: 可以使用docker拉取镜像部署和源码编译两种方式,这里选择源码编译安装。 代码拉取地址: https://github.com/xuxueli/xxl-job/tree/2.1.2 官方开发文档: https://www.xuxueli.com/xxl-job/#%E3%80%8A%E5%88%…

代码随想录算法训练营day38 | 70. 爬楼梯,509. 斐波那契数,746. 使用最小花费爬楼梯

目录 动态规划五部曲: 确定dp数组(dp table)以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 509. 斐波那契数 类型:动态规划 难度:easy 思路: f(n) f&am…

redis十种数据类型及底层原理

概述 Redis 是一个开源的高性能键值数据库,它支持多种数据类型,可以满足不同的业务需求。本文将介绍 Redis 的10种数据类型,分别是 string(字符串) hash(哈希) list(列表&#xf…

[Java优选系列第2弹]SpringMVC入门教程:从零开始搭建一个Web应用程序

想和你们分享我眼里的代码世界🗺️ 优选系列持续更新中💫 一直在等你,你终于来啦💖 绿色代表解释说明 黄色代表重点 红色代表精髓 SpringMVC是一个基于Java的Web框架,它使用了MVC&…

Linux 消息队列的创建与使用

消息队列的创建与使用 进程a发送一条消息,进程b读取消息。 a.c代码: b.c代码: 1.a进程创建向消息队列,并向消息队列中发送消息 运行a程序之前,当前系统中消息队列的数量为0: 运行一次a程序,消…

5、flink任务中可以使用哪些转换算子(Transformation)

1、什么是Flink中的转换算子 在使用 Flink DataStream API 开发流式计算任务时,可以将一个或多个 DataStream 转换成新的 DataStream,在应用程序中可以将多个数据转换算子合并成一个复杂的数据流拓扑图。 2、常用的转换算子 Flink提供了功能各异的转换算…

53.Linux day03 文件查看命令,vi/vim常用命令

今天进行了新的学习。 目录 1.cat a.查看单个文件的内容: b.查看多个文件的内容: c.将多个文件的内容连接并输出到一个新文件: d.显示带有行号的文件内容: 2.more 3.less 4.head 5.tail 6.命令模式 7.插入模式 8.图…

H3C交换机如何配置本地端口镜像并在PC上使用Wireshake抓包

环境: H3C S6520-26Q-SI version 7.1.070, Release 6326 Win 10 专业版 Wireshake Version 4.0.3 问题描述: H3C交换机如何配置本地端口镜像并在PC上使用Wireshake抓包 解决方案: 配置交换机本地端口镜像 1.进入系统视图,并创建本地镜像组1 <H3C>system-vie…

Python项目实战:基于napari的3D可视化(点云+slice)

文章目录 一、napari 简介二、napari 安装与更新三、napari【巨巨巨大的一个BUG】四、napari 使用指南4.1、菜单栏&#xff08;File View Plugins Window Help&#xff09;4.2、Window&#xff1a;layer list&#xff08;参数详解&#xff09;4.3、Window&#xff1a;layer…

Linux学习之Telnet明文漏洞

yum install telnet telnet-server xinetd -y安装软件。 systemctl start xinetd.service开启xinetd&#xff0c;systemctl start telnet.socket开启telnet。 xinetd来监控端口&#xff0c;然后把数据传给telnet。 ifconfig eth0看一下eth0网卡信息&#xff0c;。 iptable…

Linux Mint 21.3 计划于 2023 年圣诞节发布

Linux Mint 项目近日公布了基于 Ubuntu 的 Linux Mint 发行版下一个重要版本的一些初步细节&#xff0c;以及备受期待的基于 Debian 的 LMDE 6&#xff08;Linux Mint Debian Edition&#xff09;版本。 近日&#xff0c;Linux Mint 项目负责人克莱门特-勒菲弗&#xff08;Clem…

万字长文·通俗易懂·一篇包掌握——输入/输出·文件操作(c语言超详细系列)(二)

前言&#xff1a;Hello&#xff0c;大家好&#x1f618;&#xff0c;我是心跳sy&#xff0c;上一节我们主要学习了格式化输入输出的基本内容&#xff0c;这一节我们对格式化进行更加深入的了解&#xff0c;对文件概念进行介绍&#xff0c;并且对输入、输出与文件读写的基本概念…

基于 KubeSphere 的应用容器化在智能网联汽车领域的实践

公司简介 某国家级智能网联汽车研究中心成立于 2018 年&#xff0c;是担当产业发展咨询与建议、共性技术研发中心、创新成果转化的国家级创新平台&#xff0c;旨在提高我国在智能网联汽车及相关产业在全球价值链中的地位。 目前着力建设基于大数据与云计算的智能汽车云端运营…

[bug] 记录version `GLIBCXX_3.4.29‘ not found 解决方法

在使用mediapipe 这个库的时候&#xff0c;首次使用出现 GLIBCXX_3.4.29’ not found 错误&#xff0c; 看起来是安装mediapipe 的时候自动升级了 matplotlib 这个库&#xff0c;导致依赖的 libstd.so 版本不满足了&#xff0c;GLIBCXX_3.4.29 is an object from libstdc.so.…

Debian10: 安装nut服务器(UPS)

UPS说明&#xff1a; UPS的作用就不必讲了&#xff0c;我选择是SANTAKTGBOX-850&#xff0c;规格为 850VA/510W&#xff0c;可以满足所需&#xff0c;关键是Debian10自带了驱动可以支持&#xff0c;免去安装驱动&#xff0c;将UPS通过USB线连接服务器即可&#xff0c;如下图所示…

【数理知识】向量与基的内积,Matlab 代码验证

序号内容1【数理知识】向量的坐标基表示法&#xff0c;Matlab 代码验证2【数理知识】向量与基的内积&#xff0c;Matlab 代码验证 文章目录 1. 向量与基的内积2. 二维平面向量举例3. 代码验证Ref 1. 向量与基的内积 假设存在一个二维平面内的向量 a ⃗ \vec{a} a &#xff0c…

QT TLS initialization failed问题(已解决) QT基础入门【网络编程】openssl

问题: qt.network.ssl: QSslSocket::connectToHostEncrypted: TLS initialization failed 这个问题的出现主要是使用了https请求:HTTPS ≈ HTTP + SSL,即有了加密层的HTTP 所以Qt 组件库需要OpenSSL dll 文件支持HTTPS 解决: 1.加入以下两行代码获取QT是否支持opensll以…