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

二叉树——二叉树的最近公共祖先

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例 1:
在这里插入图片描述

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2:
在这里插入图片描述

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3:

输入:root = [1,2], p = 1, q = 2
输出:1

提示:

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

思路

后序遍历,父节点会接收到子节点问否是p,q,并把这个状态向上传递,直到满足条件

  • 返回值 节点
  • 参数 输入节点,p,q
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
  • 终止条件
    节点==p 或 ==q 或 为空
        if(root==p || root==q || root== NULL) return root;
  • 单次递归
    采用后序,左右中,
    左操作:设立参数left接收左子树是否有p,q,有的话left为p或q
    右操作:设立参数right接收右子树是否有p,q,有的话right为p或q
        TreeNode* left=lowestCommonAncestor(root->left,p,q);TreeNode* right=lowestCommonAncestor(root->right,p,q);

中操作:将本递归返回的参数进行判断,
左有q,右有p
左有p,右有q
上面一条成立,则此中节点为父节点

        if(left==NULL && right!=NULL) return right;if(left!=NULL && right==NULL) return left;if(left!=NULL && right!=NULL) return root;return NULL;

left和right的取值是靠终止条件返回,没找到p或q,left和right就会一直是NULL

        if(root==p || root==q || root== NULL) return root;

相关文章:

二叉树——二叉树的最近公共祖先

二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&#xff08;一…...

数据结构与算法基础-学习-14-线性表之串

一、串的定义由0-n个字符组成的有限序列。&#xff08;n>0&#xff09;二、串的相关术语1、子串串中任意个连续字符组成的子序列成为该串的子串。2、主串包含子串的串成为主串。3、字符位置字符在序列中的序号为该字符在串中的位置。4、子串位置子串第一个字符在主串中的位置…...

Mac 快捷键

目录 命令行快捷键 命令行快捷键 control d 命令行中代表发送EOF终止输入 control u 删除光标之前到行首的字符 control k 删除光标之前到行尾的字符(比较常用) control a 移动光标到行首(常用) control e 移动光标到行尾 control l 清屏&#xff0c;相当于clear命令 con…...

【微服务】-微服务环境搭建

目录 2.1 技术选型 2.2 模块设计 2.3 微服务调用 2.4 创建⽗⼯程 2.5 创建商品微服务 2.6 创建订单微服务 2.1 技术选型 持久层: SpingData Jpa 数据库: MySQL5.7 其他: SpringCloud Alibaba 技术栈 2.2 模块设计 --- shop-parent ⽗⼯程 --- shop-product-api 商品微服…...

IGKBoard(imx6ull)-ADC编程MQ-2烟雾传感器采样

文章目录1- ADC介绍2- MQ-2烟雾传感器介绍&#xff08;1&#xff09;工作原理&#xff08;2&#xff09;MQ-2应用电路3- MQ-2烟雾传感器硬件连接4- ADC驱动配置5- 编程查看当前浓度1- ADC介绍 ADC是Analog-to-Digital Converter的缩写&#xff0c;指模数转换器。真实世界的模拟…...

前端二面vue面试题总结

什么是 mixin &#xff1f; Mixin 使我们能够为 Vue 组件编写可插拔和可重用的功能。如果希望在多个组件之间重用一组组件选项&#xff0c;例如生命周期 hook、 方法等&#xff0c;则可以将其编写为 mixin&#xff0c;并在组件中简单的引用它。然后将 mixin 的内容合并到组件中…...

时间API在更新,传奇已经谢幕,但技术永远不死

&#xff08;Bill Joy(左一)&#xff0c;Vinod Khosla(左二)&#xff0c;Andy Bechtolsheim(右二)&#xff0c;Scott McNealy(右一) &#xff09; CSDN 博文征集活动&#xff08;和日期相关的代码和bug&#xff09;&#xff1a;点击这里 各位 “big guys”&#xff0c;这篇博文…...

SQL调优指南笔记22:Gathering Diagnostic Data with SQL Test Case Builder

本文为SQL Tuning Guide 第21章“Gathering Diagnostic Data with SQL Test Case Builder”的笔记。 SQL Test Case Builder 是一种工具&#xff0c;可自动收集在不同数据库实例中重现问题所需的信息。 SQL 测试用例是一组信息&#xff0c;使开发人员能够为遇到性能问题的特定…...

从0开始学python -43

Python3 正则表达式 正则表达式是一个特殊的字符序列&#xff0c;它能帮助你方便的检查一个字符串是否与某种模式匹配。 Python 自1.5版本起增加了re 模块&#xff0c;它提供 Perl 风格的正则表达式模式。 re 模块使 Python 语言拥有全部的正则表达式功能。 compile 函数根…...

Kafka基本原理

总述 简介 Kafka是最初由Linkedin公司开发&#xff0c;是一个分布式、支持分区的&#xff08;partition&#xff09;、多副本的&#xff08;replica&#xff09;&#xff0c;基于zookeeper协调的分布式消息系统&#xff0c;它的最大的特性就是可以实时的处理大量数据以满足各…...

css3的重点内容

css3的重点内容 浮动 父级边框塌陷问题 浮动的清除 clear:left; //清除左侧浮动 clear:right; //清除右侧浮动 clear:both; //清除两侧浮动解决方案 增加父级元素的高度增加一个空的div&#xff0c;之后清除浮动通过overflow来进行相关元素的修剪给父类添加相应的伪类元素…...

《Roller: Fast and Efficient Tensor Compilation for Deep Learning》

《Roller: Fast and Efficient Tensor Compilation for Deep Learning》 用于深度学习 快速高效的张量编译器 作者 微软亚洲研究院以及多伦多大学等多所高校 摘要 当前编译为了产生高效的kernel时&#xff0c;搜索空间大&#xff0c;通常使用机器学习的方法 找到最优的方案…...

顺丰同城测试开发一面 49min答案,全文7000字,面试总结都在这里了

今天给大家分享一份顺丰同城的测试开发一面面试真题。老规矩&#xff0c;当你看到这份面试题的时候&#xff0c;先不要着急去看答案&#xff0c;你可以想想假如你在面试现场&#xff0c;你会怎么回答&#xff1f;这个思考的过程其实也是很重要的。 全文7000字干货&#xff0c;…...

docker启动容器服务之后访问失败

关于docker启动容器服务之后&#xff0c;宿主机访问失败&#xff08;解决方法&#xff09; 注&#xff1a;在进行docker容器启动宿主机进行容器访问时&#xff0c;无需进行网络的配置&#xff0c;docker容器在启动时会自动解决 第一种原因及修改方法 在进行启动的时候&#…...

GraalVM-云原生时代的JVM(Java)

文章目录一、GraalVM是什么&#xff1f;二、GraalVM有哪些特点&#xff1f;2.1、高性能2.2、多语言支持2.3、互操作性2.4、安全性三、GraalVM的应用效果3.1、提高性能3.2、简化开发3.3、降低成本3.4、节省资源3.5、支持云环境四、使用GraalVM编译springboot应用程序4.1、下载并…...

如何外网登录访问瑞友天翼应用虚拟化系统?——快解析内网端口映射方案

瑞友天翼应用虚拟化系统&#xff08;GWT System&#xff09;是国内具有自主知识产权的应用虚拟化平台&#xff0c;是基于服务器计算&#xff08;Server-based Computing&#xff09;的应用虚拟化平台。如何将内网平台提供到互联网上外网访问&#xff0c;是我们比较关注的问题。…...

蓝海彤翔执行副总裁张加廷接受【联播苏州】独家专访

今年春节档&#xff0c;科幻类电影《流浪地球2》票房口碑双丰收&#xff0c;截至目前&#xff0c;累计票房已破 38 亿&#xff0c;淘票票评分 9.6 &#xff0c;影片的特效质感可以媲美国际顶尖水平。其中&#xff0c;蓝海彤翔为影片的后期制作提供了出色的渲染服务。2月21日&am…...

iOS Airplay Screen Mirroring 同屏技术详解

投屏技术已经被大量用在身边的产品&#xff0c;比如电视投屏&#xff0c;投影仪&#xff0c;视频会议产品中。 在iOS平台外的其他平台中都已经有非常成熟的标准和实现。但在封闭的苹果iOS和Mac系统中&#xff0c;苹果使用私有的Airplay协议进行多屏互动&#xff0c;只开放给自己…...

更新 Python 100道基础入门检测练习题【下篇】(附答案)

前言 大家早好、午好、晚好吖 ❤ ~ 爆肝更新 Python 100道基础入门练习题【篇上】 更多精彩内容、资源皆可点击文章下方名片获取此处跳转 实例021&#xff1a;猴子偷桃 题目&#xff1a; 猴子吃桃问题&#xff1a;猴子第一天摘下若干个桃子&#xff0c;当即吃了一半&#xf…...

[RDMA-高级计算机网络report] Congestion Control for Large-Scale RDMA Departments

本文主要解决的问题是在RoCEv2体系中&#xff0c;基于优先级的拥塞控制PFC是一种粗粒度的机制。 它在端口&#xff08;或端口加优先级&#xff09;级别上运行&#xff0c;并且不区分流。PAUSE机制是基于每个端口&#xff08;和优先级&#xff09;的&#xff0c;而不是基于每个流…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...