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

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

题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems
特别鸣谢:来自夸夸群的 醉笑陪公看落花@知乎,王不懂不懂@知乎,QFIUNE@csdn
感谢醉笑陪公看落花@知乎 倾囊相授,感谢小伙伴们督促学习,一起进步

文章目录

  • 路径法
  • 标记法 - 记录每一个节点是不是p,q的公共节点

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

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

路径法

基本思路:

  • 找p的路径
  • 找q的路径
  • 二者不相等路径遇到的第一个不相等的节点即是最近公共祖先

其中,找路径有两种方法

  • 把二叉树转换为数组,根据父节点和左右孩子的下标关系,找所有祖先
  • 参考Dijstra算法里面路径存储的想法,初始话一个数组,数组根据下标存父节点的值 参考博文 leetcode 743. 网络延迟时间- 有向图 - 图的一些小知识点 - 迪杰斯特拉(dijkstra)-弗洛伊德(Floyd)
    在这里插入图片描述

标记法 - 记录每一个节点是不是p,q的公共节点

后续遍历+ 递归可以实现

# Definition for a binary tree node.
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':def f(root,p,q):if not root:return 0r1 = f(root.left,p,q)if not isinstance(r1,int): return r1r2 = f(root.right,p,q)if not isinstance(r2,int): return r2ans = 1 if root == p else 2 if root == q else 0r3 = r1+r2 + ansif r3 == 3:return rootreturn r1+r2 + ansreturn f(root, p, q)

tips:

  • not 0: True
  • not None: True

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

ResultMap 关系映射详细使用

关于MyBatis中ResultMap的详细使用ResultMap简介使用ResultMap创建sql 模仿一对多或多对一关系创建数据库创建SpringBoot项目 导入mybatis依赖pojo---------------------------------------------------------------------------------StudentTeacherdao----------------------…...

SQL server安装时显示重启计算机失败问题解决办法

SQL server安装时显示重启计算机失败问题解决办法参考文章: (1)SQL server安装时显示重启计算机失败问题解决办法 (2)https://www.cnblogs.com/netflix/p/12074481.html 备忘一下。...

Linux系统编程系列(一)

系统软件属于系统的底层,与内核和系统核心库直接进行交互,系统编程则是进行系统软件的关键,熟悉系统编程可以重现如shell、vim、gcc等系统软件。而作为一个高级C/C编程人员,往往需要在底层进行多次调用,学习Linux系统编…...

PAT A 1133 AC代码(两种输出方式)

跑一遍序列,根据要求分别将结点标记存入v1、v2、v3 我二刷时用ans数组合并了v1、v2、v3,再进行输出会方便很多,不然的话需要分别考虑v1、v2、v3是否为空的情况(原本我是那样写的,如果是那样写的同学要注意一下只有v2是…...

numpy练习题

numpy 练习题 numpy 的array操作 1.导入numpy库 import numpy as np2.建立一个一维数组 a 初始化为[4,5,6], (1)输出a 的类型(type)(2)输出a的各维度的大小(shape)(3)输出 a的第一个元素(值为4) anp.ar…...

机器学习中分类与聚类的本质区别

机器学习中分类与聚类的本质区别 机器学习中有两类的大问题,一个是分类,一个是聚类。 在我们的生活中,我们常常没有过多的去区分这两个概念,觉得聚类就是分类,分类也差不多就是聚类,下面,我们就…...

SDKD 2021 C1 8th Round

A - Parity 签到&#xff0c;根据奇数偶数的预算性质。 #include <iostream> #include <cstdio> using namespace std; int a,b,k,ans; int main() {cin>>b>>k;for(int ik-1;i>0;i--){scanf("%d",&a);if(b%2&&a%2||a%2&…...

copy代码常出的报错~持续更新

一 AttributeError: DataFrame object has no attribute ixpandas的1.0.0版本后&#xff0c;已经对该函数进行了升级和重构。 只需要将 ix改成 loc二在pycharm中使用 %matplotlib inline 语句会报错 改成 删掉这行代码&#xff0c;用 plt.show() 展示图表%matplotlib inlin…...

极客时间架构师训练营,实战案例

正文 我在做技术面试官的时候&#xff0c;在问完问题后&#xff0c;照例会问一句&#xff1a;你期望的工资是多少&#xff1f;对此&#xff0c;我只会记录下候选人的回答然后上报&#xff0c;没有同意权&#xff0c;更没有批驳权。 判断候选人能否通过面试&#xff0c;主要看…...

暑假acwing算法总结11:STL总结

1、vector 倍增自变长数组&#xff0c;插入均摊o(1)size() 返回元素个数empty() 判断是否为空clear() 清空front()/back() 返回第一/最后一个数push_back()/pop_back() 添加/删除元素begin()/end() 首/尾迭代器遍历方式 for(int i0;i<s.size();i)cout<<a[i]<< …...

事件循环机制(Event Loop)刨根问底

事件循环是什么&#xff1f; 为什么有事件循环机制 因为js是单线程的&#xff0c;注意&#xff0c;浏览器是多线程的。浏览器只给一个线程给js渲染&#xff0c; 假设是多线程&#xff0c;可能会存在这种情况&#xff1a; 若一个线程要操作dom,另一个线程要删除dom&#xff0c;就…...

Kafka学习----Kafka高级理论

Kafka高级理论一 . Kafka 工作流程二. Kafka文件存储机制①. Kafka文件存储机制②. index文件和log文件详解三. Kafka 生产者①. 分区策略1. 分区的原因2. 分区的原则②. 数据可靠性保证1. 副本数据同步策略2. ISR3. ack 应答机制4. 故障处理细节③. Exactly Once 语义四. Kafk…...

wxWidgets:窗口删除

wxWidgets:窗口删除 wxWidgets:窗口删除关闭窗口默认窗口关闭行为用户呼叫退出菜单优雅地退出应用程序自动删除子窗口其他种类的窗户wxWidgets:窗口删除 窗口删除可能是一个令人困惑的主题,因此提供此概述是为了帮助您明确删除窗口的时间和方式,或响应用户关闭窗口的请求…...

Node.js-EJS模板

EJS是一个JavaScript模版库&#xff0c;用来将EJS模版结合着JSON数据转换为HTML 并且可以直接在模版中写JavaScript的语法 安装ejs包 //控制台输入 npm i ejs简单示例 let template <h1>Hello, <% name %></h1> let data {name: World }let renderStr …...

Windows没有MySQL服务及MySQL无法启动解决办法

下载MySQL并把MySQL的路径配置到系统环境后执行命令&#xff1a;mysql -u root -p 报错&#xff1a;ERROR 2003 (HY000): Cant connect to MySQL server on localhost (10061) 猜测原因可能是windows没有mysql服务或mysql服务没有启动&#xff0c;这篇文章主要讲windows没有my…...

采坑记录之node-sass

node-sass这货很容易安装失败 下面是node-sass官网给出的对应node.js版本的图 一定要按照node-sass官网给出的对应node.js版本来安装&#xff0c;不然很容易安装失败 下面是sass-loader版本图 我自己安装的是node.js 14.x版本的&#xff0c;对应的node-sass的版本是4.14.x&a…...

C# 打包windows服务安装包后,安装后自动启动服务

在服务的安装程序&#xff0c;通常是ProjectInstaller&#xff0c;重写他的Commit方法 public override void Commit(IDictionary savedState){base.Commit(savedState);ServiceController sc new ServiceController("你的服务名称");if (sc.Status.Equals(Service…...

MATLAB 数学应用 微分方程 时滞微分方程 ddesd

求解带有常规时滞的时滞微分方程 (DDE) 语法 sol ddesd(ddefun,delays,history,tspan) sol ddesd(ddefun,delays,history,tspan,options) 参数 参数说明ddefun用于对微分方程 y′(t) f(t,y(t),y(d(1),…,y(d(k))) 的右侧进行计算的函数句柄。此函数必须为以下形式&#…...

Java 从多线程到并发编程(七)—— wait notify 生产者消费者问题 管程法 信号灯法

文章目录前言 &#xff65;ᴗ&#xff65;wait 与 notifynotify 和 notifyAll深入了解 阻塞线程的状态切换生产者消费者模型wait notify深入一点管程法管程法 仓库管程法 生产者管程法 消费者管程法 main调用管程法结果if还是while信号灯法总结 ◡前言 &#xff65;ᴗ&#xff…...

雨课堂期末考试答案----查了好多份答案,一道一道的进行查找正确答案,基本可以保证是正确答案

1.主观题 (10分) 工程为何总是伴随着风险?导致工程风险的因素有哪些? 2.判断题 (1分) 目前对水利工程价值的伦理判断基本是遵循功利主义原则。()对 3.单选题 (1分) 下列哪一项不属于工程实践全球性特征?( )C A 生态性 B 深远性 C 社会性 D 整体性 4.单选题 (1分) …...

弘辽科技:成为拼多多商家要什么要求?收费吗?

现在也有不少人想要入驻拼多多&#xff0c;但是想要成为拼多多的商家也需要满足对应的要求&#xff0c;同时也想要了解成为拼多多商家是否需要收费&#xff0c;我马上就来给各位卖家们介绍。 拼多多商家入驻平台分四种店铺&#xff0c;这里小编介绍一下旗舰店、专营店入驻基本条…...

辗转相除求最大公约数

#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h>int main() {int a 0;int b 0;int tmp 0;scanf("%d %d", &a, &b);if (a < b){tmp a;a b;b tmp;}if (a%b ! 0){tmp a;a b;b tmp%b;}printf("%d\n", b);return 0; }...

K-means笔记

K-means算法 算法过程&#xff1a; 从N个样本数据中随机选取K个对象作为初始的聚类中心。分别计算每个样本到这各个聚类中心的距离&#xff0c;并将对象归于距离最短的聚类群中。所有样本计算完后&#xff0c;重新计算K个聚类中心。与前一次计算得到得聚类中心比较。如果聚类中…...

39.【Axure 10 】交元件(元件组)交互事件

鼠标相关交互事件 【高】单击时 元件(元件组)的是鼠标单击事件&#xff0c;可以实现鼠标单击的触发的交互事件。 【中】双击事件 元件(元件组)的是鼠标双击事件&#xff0c;作为触发条件。同时也是双击页面任何地方可触发。 【中】鼠标右击事件 元件(元件组)的鼠标右击是…...

hive常用函数

1. 获取某个字段的值 regexp_extract(message, (.*?)properties(.*?),, 2) as value 2....

手写Promise.all()方法

有1个promise报错了&#xff0c;其他的promis会执行吗&#xff1f; 会的&#xff0c;因为Promsie在实例化时候就已经执行完了。手写Promise.all()方法 function PromiseAll(promiseArray){//返回的一定是个proimsereturn new Promise((resolve,reject)>{//首先判断传入的是…...

PAT A 1133 AC代码(两种输出方式)

跑一遍序列&#xff0c;根据要求分别将结点标记存入v1、v2、v3 我二刷时用ans数组合并了v1、v2、v3&#xff0c;再进行输出会方便很多&#xff0c;不然的话需要分别考虑v1、v2、v3是否为空的情况&#xff08;原本我是那样写的&#xff0c;如果是那样写的同学要注意一下只有v2是…...

你不知道的JS思考题

思考题 1、对比空值和对象的类型 思路&#xff1a; typeof null "object" typeof {} "object"答案 var a null ; (!a && tpeof a object); 补充&#xff1a; 内置类型typeof null "object" 祖传bug undefined "undefined&…...

python中字符码和字符串的相互转换

来源&#xff1a; 博客园...

Linux驱动---IO模型

1、什么是IO 在计算机系统中I/O就是输入和输出的意思&#xff0c;只要具有输入输出类型的交互系统都可以认为是I/O系统 也可以说I/O是整个操作系统数据交换与人机交互的通道 针对不同的操作对象&#xff0c; 可以划分为磁盘I/O模型&#xff0c;网络I/O模型&#xff0c;内存映…...

Unity3D ML-Agent-0.8.1 学习七(例子源码分析1)

Unity3D ML-Agent-0.8.1 学习七&#xff08;例子源码分析1&#xff09;&#xff09;写的目的例子Basic3DBallGridWorld总结写的目的 本篇想分享下看例子中的源码分析&#xff0c;其实也就是一些我理解之后的注释&#xff0c;一些思路&#xff0c;希望对你有帮助。 例子 Basi…...

【Unity-实现小功能-001】骰子功能

最近在做飞行棋项目&#xff0c;实现了一个投掷骰子的小功能。其中使用的Uniy自带的物理碰撞产生随机点数的功能。 设计要点&#xff1a; 利用Unity自带的物理系统进行投掷&#xff0c;与周围环境进行碰撞&#xff0c;增加随机性。利用触发器判断点数。 模型结构&#xff1a;…...

黑马程序员-“骑士飞行棋”游戏基本逻辑和一点思考

------- Windows Phone 7手机开发、.Net培训、期待与您交流&#xff01; ------- 游戏不用介绍了&#xff0c;大家看过视频的都知道了&#xff08;我还没看飞行棋的视频讲解&#xff09; 游戏没有用太复杂的函数&#xff0c;各种语言都可以实现&#xff0c;所以我给出伪代码…...

python调用打印机驱动下载_不要驱动,简单粗暴的用树莓派驱动USB打印机

网上很多文章都是再说如何用树莓派来做一个通用打印服务器&#xff0c;但是在很多应用场景下&#xff0c;配置CUPS什么的真的是自己zuo自己die的好途径&#xff0c;各类linux下的驱动配置起来令人吐血。而驱动各种热敏票据打印机&#xff0c;比如打胶带啊&#xff0c;二维码贴纸…...

Starday为什么是跨境电商卖家的不二之选?

据国内海关统计显示&#xff0c;近5年来&#xff0c;中国跨境电商规模增长近10倍&#xff0c;年增长率在30%以上&#xff0c;占国际贸易近40%。基于流量模式的跨境电商直播、垂直跨境电商等新模式蓬勃发展&#xff0c;近几年跨境电商一直不断地在深度融合发展&#xff0c;加之疫…...

usb打印机linux识别不了怎么办,安装打印机驱动时搜索不到打印机怎么办 安装打印机驱动无法识别usb怎么解决...

对于熟悉安装打印机驱动安装步骤的朋友来说&#xff0c;安装驱动一定非常的简单&#xff0c;但是如果你是第一次安装&#xff0c;会遇到很多问题不知道怎么解决&#xff0c;比如安装打印机驱动时搜索不到打印机的问题&#xff0c;安装打印机驱动无法识别usb的问题等等&#xff…...

终于有阿里p9架构师分享出困扰我多年的分布式系统开发实战文档

前言 都说程序员工资高、待遇好&#xff0c; 2022 金九银十到了&#xff0c;你的小目标是 30K、40K&#xff0c;还是 16薪的 20K&#xff1f;作为一名 Java 开发工程师&#xff0c;当能力可以满足公司业务需求时&#xff0c;拿到超预期的 Offer 并不算难。然而&#xff0c;提升…...

【英语语法】 for

1、for 在英语学习中&#xff0c;我们经常用到&#xff0c;for 做连词时引导原因状语从句&#xff0c;主要表示理由&#xff0c;用于引导的分句对前面的话进行解释&#xff0c;起到补充说明的意思&#xff0c;常用逗号把它和前面的分句分开。例如&#xff1a; Humanity had be…...

Linux摄像头驱动第一篇之虚拟摄像头驱动vivi.c

本文学习自韦东山老师的摄像头驱动模块 目录 一 摄像头驱动程序学习切入点以及V4L2模型概览 二 简析虚拟视频驱动 VIVI.C 2.1 初始化、设置、注册过程2.2 简析vivi.c的open,read,write,ioctl过程 三 虚拟摄像头驱动的启动过程简析 3.1 查看虚拟摄像头应用程序启动虚拟摄像…...

【转载】Linux摄像头驱动1——vivid

Linux摄像头驱动学习第一篇&#xff0c;对虚拟视频驱动Virtual Video Driver(vivid)进行测试、分析、编写。 V4L2(Video for Linux two)是Linux内核中关于视频设备的内核驱动框架&#xff0c;为上层的访问底层的视频设备提供了统一的接口。 V4L2可以支持多种设备,它可以有以下…...

【通知】2021-2022-1线性代数课程答疑安排

2021-2022-1线性代数课程答疑安排 本学期线性代数课程答疑安排如下&#xff1a; 答疑时间&#xff1a;每周二 13&#xff1a;00-14&#xff1a;30&#xff1b;答疑地点&#xff1a;教七楼202&#xff08;信息教研室&#xff09;&#xff1b; 答疑教师排班如下: 第五周&…...

工业互联网标识解析的常见应用

工业互联网标识解析是工业互联网重要的网络基础设施&#xff0c;为工业设备、机器、物料、零部件和产品提供编码、注册与解析服务&#xff0c;其体系主要由标识编码、标识数据服务、标识解析系统组成&#xff0c;是实现工业全要素、各个环节信息互通的重要环节&#xff0c;是引…...

cpu设计和实现(异常和中断)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 异常和中断几乎是cpu最重要的特性。而异常和中断&#xff0c;本质上其实是一回事。很多熟悉mips的朋友&#xff0c;应该都听过这么一个词&#xff…...

基于AADL的模型设计与仿真分析技术

AADL&#xff08;Architecture Analysis and Design language&#xff09;是一种应用于嵌入式系统领域的体系结构建模语言&#xff0c;支持航空、航天、汽车等领域复杂实时的安全关键系统的设计与分析。AADL具有语法简单、功能强大、可扩展等优点&#xff0c;能够对嵌入式软件的…...

中国地质大学计算机研究生考试目录,2017年中国地质大学(武汉)资源学院考研专业目录及考试科目...

学科专业名称及代码、研究方向考试科目招生人数指导教师备注资源学院(102)027-67883627250推免&#xff1a;77非全日制&#xff1a;90矿物学、岩石学、矿床学(070901)7推免&#xff1a;4(01)(全日制)成矿作用地球化学①101|思想政治理论 ②201|英语一 ③610|高等数学④824|矿床…...

了解指针(5)-- 指针和函数

就像数组名是指向数组的第一个元素的常指针一样&#xff0c;函数名也是指向函数的常指针。可以声明一个指向函数的指针变量&#xff0c;并且用这个指针调用其他函数&#xff08;只要这个函数和你的函数指针在签名、返回、参数值方面一致即可&#xff09;。例1&#xff1a;long …...

使用Putty在机群中不用输入密码自由傲游

如果服务器的机群有几十台&#xff0c;甚至更多&#xff0c;你会不会觉得远程登录的时候频繁的输入密码很累呢&#xff1f;如下的方法就可以免除您这一烦恼。首先下载putty-0.60-installer.exe&#xff0c;到http://www.chiark.greenend.org.uk/~sgtatham/putty/download.html …...

Android开发性能优化大总结

一.Android相关 1. 采用硬件加速&#xff0c;在androidmanifest.xml中application添加android:hardwareAccelerated"true"。不过这个需要在android 3.0才可以使用。android4.0这个选项是默认开启的。 2. View中设置缓存属性.setDrawingCache为true. 3. 优化你的…...

QOS 总结

1.QOS的两种模型 QoS的实现模型主要有集成服务模型&#xff08;IntegratedService&#xff09;和差别服务模型&#xff08;DifferentiatedService&#xff09;。集成服务模型是端到端的基于流的QoS技术&#xff0c;它通过信令向网络申请特定的QoS服务&#xff0c;网络在流量参…...

SVN学习总结(2)——SVN冲突解决

2019独角兽企业重金招聘Python工程师标准>>> 在我们用VS进行项目合作开发的过程中&#xff0c;SVN的提交控制是至关重要的&#xff0c;大家不可避免的都遇到过SVN冲突的问题&#xff0c;开发的时候&#xff0c;应该认真学习SVN的知识&#xff0c;减少冲突&#xff0…...