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

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

文章目录

  • 一、题目描述
      • 示例 1
      • 示例 2
      • 示例 3
  • 二、代码
  • 三、解题思路


一、题目描述

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

百度百科中最近公共祖先的定义为:“对于有根树 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, 10^5] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

二、代码

代码如下:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':p_father = []q_father = []def findp(r,path):if r.val == p.val:p_father.extend(path)p_father.append(r)returnif r.left != None:path.append(r)findp(r.left,path)path.pop()if r.right != None:path.append(r)findp(r.right,path)path.pop()def findq(r,path):if r.val == q.val:q_father.extend(path)q_father.append(r)returnif r.left != None:path.append(r)findq(r.left,path)path.pop()if r.right != None:path.append(r)findq(r.right,path)path.pop()findp(root,[])findq(root,[])presult = rootfor i in range(min(len(q_father),len(p_father))):if q_father[i] == p_father[i]:result = q_father[i]continueelse:breakreturn result

三、解题思路

本题在235. 二叉搜索树的最近公共祖先
的基础上将二叉搜索树改为二叉树,那么根据我们之前搜索p,q节点的所有父节点的思路来看,搜索方式有所不同,不能通过二叉搜索树的规律来快速找到对应p,q节点,但也可以通过一步一步试错的方式慢慢找到所有的父节点,解题思路同235. 二叉搜索树的最近公共祖先
一致,通过找出p,q节点所有的父节点列表,然后找出列表的最大公共子列表后,最后一个元素即为最近公共祖先。

相关文章:

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

文章目录 一、题目描述示例 1示例 2示例 3 二、代码三、解题思路 一、题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满…...

WPF中DataGrid控件绑定数据源

步骤 创建数据源&#xff1a;首先&#xff0c;我们需要创建一个数据源&#xff0c;可以是一个集合&#xff08;如List、ObservableCollection等&#xff09;&#xff0c;也可以是一个DataTable对象。数据源中的每个元素代表一行数据。 设置DataGrid的ItemsSource属性&#xff…...

Linux arm64 set_memory_ro/rw函数

文章目录 一、函数简介1.1 简介1.2 change_memory_common1.3 __change_memory_common 二、apply_to_page_range函数2.1 apply_to_page_range2.2 apply_to_p4d_range2.3 apply_to_pud_range2.4 apply_to_pmd_range2.5 apply_to_pte_range 三、hook系统调用参考资料 一、函数简介…...

安达发|APS排单软件中甘特图的应用

近几年来&#xff0c;企业对生产效率和管理水平的要求越来越高。为了提高生产效率&#xff0c;降低生产成本&#xff0c;许多企业开始引入先进的生产计划与调度系统&#xff08;APS&#xff09;&#xff0c;实现生产过程的自动化、智能化管理。APS排产软件是一种能够根据企业的…...

快速上手Linux基础开发工具

目录 软件包管理器 概念理解 用法示例 - 以yum为例 vim 模式的切换 常用操作 插件和配置 gcc/g gdb make / makefile 软件包管理器 概念理解 在Linux下安装软件的话&#xff0c;一个比较原始的办法是下载程序的源代码&#xff0c;然后进行编译&#xff0c;进而得到…...

【开发工具】idea 的全局搜索快捷键(Ctrl+shift+F)失效

文章目录 前言1. 取消 输入法的快捷键&#xff08;推荐使用&#xff09;2.更改 idea的快捷键3. 热键占用总结 前言 当你发现在idea 中看到用于全局搜索的快捷键就是 CtrlshiftF&#xff0c;可是怎么按都不管用的时候&#xff0c;你就不要再执着于自己的操作继续狂点电脑按键了…...

港联证券:“火箭蛋”来袭 蛋价涨势能否延续?

上个交易周&#xff08;9月11日至15日&#xff09;&#xff0c;鸡蛋期货商场呈现了意想不到的涨势。9月15日&#xff0c;鸡蛋期货多个合约大涨&#xff0c;其中2310合约涨超5.6%&#xff0c;主力合约2311盘中两度触及涨停&#xff0c;最终收涨6%。业内人士以为&#xff0c;鸡蛋…...

Vue3_vite

使用Vue-cli创建 使用vite创建 Composition API 组合API setup 1.Vue3中的一个新的配置项,值为一个函数 2.可以将组件中所用到的数据,方法等配置在setup中. 3.setup函数的两种返回值 3.1若返回一个对象,则对象中的属性,方法,在模板中均可以直接使用. 3.2若返回一个渲染函数…...

python-字符串去掉空格的常见方法

python提供了去掉字符串空格的方法&#xff0c;可以满足大部分需求。 但在实际应用中&#xff0c;还需要灵活借助python其他方法&#xff0c;来实现字符串空格的删除。 比如&#xff0c;去掉字符串的全部空格、字符串连续空格保留一个等&#xff0c;都需要结合其他的方法来实现…...

如何写出一个成熟的线上线下结合的营销方案?

分享一下咱们案例库里策划的一个线上线下结合的活动的案例。 这个活动是为了推广一个新品牌&#xff0c;增加品牌知名度和用户粘性。 你可以根据以下几个要点来进行活动策划&#xff1a; 1、目标&#xff1a; 让目标用户了解并喜欢新品牌&#xff0c;激发用户参与和分享&am…...

Vc - Qt - “扩张“的窗口

该示例演示了一个"扩张的窗口"&#xff0c;主窗口的布局为水平布局&#xff0c;内置两个子窗口&#xff0c;采用定时器设置左边窗口的宽度&#xff0c;达到控制"扩张"的目的。 #include <QApplication> #include <QWidget> #include <QHBox…...

vue学习-02vue入门之组件

删除Vue-cli预设 在用户根目录下(C:\Users\你的用户名)这个地址里有一个.vuerc 文件,修改或删除配置 组件 Props(组件之间的数据传递) Prop 的大小写 (camelCase vs kebab-case)不敏感Prop 类型: String Number Boolean Array Object Date Function Symbol传递静态或动态 Pr…...

解决Pycharm使用Conda激活环境失败的问题

Q:公司电脑终端使用powershell来激活conda环境时报错? 同时手动打开powershell报"profile.ps1” 无法被加载的错误 A: 1,手动打开powershell&#xff0c;设置管理员打开 2,打开powershell 打开 PowerShell 终端&#xff0c;并输入以下命令&#xff1a;Get-ExecutionPo…...

SpringSecurity 核心组件

文章目录 SpringSecurity 结构组件&#xff1a;SecurityContextHolder组件&#xff1a;Authentication组件&#xff1a;UserDetailsService组件&#xff1a;GrantedAuthority组件总结 SpringSecurity 结构 在SpringSecurity中的jar分为4个&#xff0c;作用分别为 jar作用spri…...

【Vue】快速入门和生命周期

目录 前言 一、vue的介绍 1. Vue.js是什么&#xff1f; 2. 库和框架的区别 3.基本概念和用法&#xff1a; 二、MVVM的介绍 1. 什么是MVVM&#xff1f; 2. MVVM的组成部分 3. MVVM的工作流程 4. MVVM的优势 5. MVVM的应用场景 三、vue实例 1.模板语法&#xff1a; …...

JVM架构和内存管理优化

Java虚拟机&#xff08;JVM&#xff09;是Java编程语言的核心组件&#xff0c;负责执行Java字节码并提供运行时环境&#xff0c;使得Java程序可以在不同的平台上运行。了解JVM的工作原理和内存管理对于优化代码性能和理解Java的内存管理和垃圾收集机制非常重要。在本文中&#…...

C语言——贪吃蛇小游戏

目录 一、ncurse 1.1 为什么需要用ncurse&#xff1a; 1.2 ncurse的输入输出&#xff1a; 1.2.1 如何使用ncurse&#xff1a; 1.2.2 编译ncurse的程序&#xff1a; 1.2.3 测试输入一个按键ncurse的响应速度&#xff1a; 1.3 ncurse上下左右键获取&#xff1a; 1.3.1 如…...

PHP8中获取并删除数组中第一个元素-PHP8知识详解

我在上一节关于数组的教程&#xff0c;讲的是在php8中获取并删除数组中最后一个元素&#xff0c;今天分享的是相反的&#xff1a;PHP8中获取并删除数组中第一个元素。 回顾一下昨天的知识&#xff0c;array_pop()函数将返回数组的最后一个元素&#xff0c;今天学习的是使用arr…...

EtherCAT 总线型 4 轴电机控制卡解决方案

 技术特点  支持标准 100M/s 带宽全双工 EtherCAT 总线网络接口及 CoE 通信协议一 进一出&#xff08;RJ45 接口&#xff09;&#xff0c;支持多组动态 PDO 分组和对象字典的自动映射&#xff0c;支持站 号 ID 的自动设置与保存&#xff0c;支持 SDO 的电机参数设置与…...

Upload-labs十六和十七关

目录 第十六关第十七关 第十六关 直接上传php文件判断限制方式&#xff1a; 同第十五关白名单限制 第十六关源码&#xff1a; 代码逻辑判断了后缀名、content-type&#xff0c;以及利用imagecreatefromgif判断是否为gif图片&#xff0c;最后再做了一次二次渲染 第71行检测…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...