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

leetcode235. 二叉搜索树的最近公共祖先(java)

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

  • 题目描述
    • 递归 + 剪枝
    • 代码演示:
  • 上期经典

题目描述

难度 - 中等
LC235 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

在这里插入图片描述

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

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

说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

在这里插入图片描述

递归 + 剪枝

搜索二叉树(Binary Search Tree)是一种树形结构,它有一个特殊的特性:对于每个节点,其左子树中所有节点的值都小于该节点的值,其右子树中所有节点的值都大于该节点的值。这种特性使得搜索效率非常高。
搜索二叉树具有以下特点:

1.每个节点最多只有两个子节点,分别称为左子节点和右子节点。
2.左子节点小于父节点,右子节点大于父节点。
3.没有重复的节点。

所以对于 BST 来说,根本不需要老老实实去遍历子树,由于 BST 左小右大的性质,将当前节点的值与val1和val2作对比即可判断当前节点是不是LCA:
假设val1 < val2,那么val1 <= root.val <= val2则说明当前节点就是LCA;若root.val比val1还小,则需要去值更大的右子树寻找LCA;若root.val比val2还大,则需要去值更小的左子树寻找最近公共祖先。

题目中说了两个节点肯定在这颗树上,因此可以省去不在的情况的判断。

代码演示:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/class Solution {TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 保证 val1 较小,val2 较大int val1 = Math.min(p.val, q.val);int val2 = Math.max(p.val, q.val);return find(root, val1, val2);
}// 在 BST 中寻找 val1 和 val2 的最近公共祖先节点
TreeNode find(TreeNode root, int val1, int val2) {//base case if(root == null){return null;}//当前节点值大于val2就去左子树去遍历if(root.val > val2){return find(root.left,val1,val2);}// //当前节点值小于val1就去右子树去遍历if(root.val < val1){return find(root.right,val1,val2);}//如果 val1 <= root.val <= val2 说明当前节点就是最近公共祖先return root;
}
}

上期经典

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

相关文章:

leetcode235. 二叉搜索树的最近公共祖先(java)

二叉搜索树的最近公共祖先 题目描述递归 剪枝代码演示&#xff1a; 上期经典 题目描述 难度 - 中等 LC235 二叉搜索树的最近公共祖先 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个结点 p、q…...

2023物联网新动向:WEB组态除了用于数据展示,也支持搭建业务逻辑,提供与蓝图连线和NodeRed规则链类似的可视化编程能力

前言 组态编辑在工业控制、物联网场景中十分常见&#xff0c;越来越多的物联网平台也把组态作为一项标配功能。 物联网产业链自下往上由“端 - 边 - 管 - 云 -用”多个环节构成&#xff0c;组态通常是用于搭建数据展示类型的应用&#xff0c;而随着系统集成度越来越高&#x…...

react将文件转为base64进行上传

需求 将图片、pdf、word、excel等文件进行上传。图片、pdf等调接口A、word、excel等附件调接口B。接口关于文件是base64格式的参数 业务场景 上传资源&#xff0c;区分影像与附件 逻辑思路 使用原生input标签&#xff0c;typefile&#xff0c;进行上传上传后的回调&#x…...

生成式人工智能能否使数字孪生在能源和公用事业行业成为现实?

推荐&#xff1a;使用 NSDT场景编辑器 快速搭建3D应用场景 克服障碍&#xff0c;优化数字孪生优势 要实现数字孪生的优势&#xff0c;您需要数据和逻辑集成层以及基于角色的演示。如图 1 所示&#xff0c;在任何资产密集型行业&#xff08;如能源和公用事业&#xff09;中&…...

SpringBoot集成JWT token实现权限验证

JWTJSON Web Token 1. JWT的组成 JWTHeader,Payload,Signature>abc.def.xyz 地址&#xff1a;JSON Web Tokens - jwt.er 1.1 Header Header:标头。 两个组成部分&#xff1a;令牌的类型&#xff08;JWT&#xff09;和所使用的签名算法&#xff0c;经过Base64 Url编码后形成…...

算法通关村第11关【青铜】| 位运算基础

1.数字在计算机中的表示 原码、反码和补码都是计算机中用于表示有符号整数的方式。它们的使用旨在解决计算机硬件中的溢出和算术运算问题。 原码&#xff08;Sign-Magnitude&#xff09;&#xff1a; 原码最简单&#xff0c;它的表示方式是用最高位表示符号位&#xff0c;0表示…...

无涯教程-Android - RadioGroup函数

RadioGroup类用于单选按钮集。 如果我们选中属于某个单选按钮组的一个单选按钮,它将自动取消选中同一组中以前选中的任何单选按钮。 RadioGroup属性 以下是与RadioGroup控制相关的重要属性。您可以查看Android官方文档以获取属性的完整列表以及可以在运行时更改这些属性的相关…...

降噪音频转录 Krisp: v1.40.7 Crack

主打人工智能降噪服务的初创公司「Krisp」近期宣布推出音频转录功能&#xff0c;能对电话和视频会议进行实时设备转录。该软件还整合的ChatGPT&#xff0c;以便快速总结内容&#xff0c;开放测试版于今天上线。 随着线上会议越来越频繁&#xff0c;会议转录已成为团队工作的重…...

基于React实现:弹窗组件与Promise的有机结合

背景 弹窗在现代应用中是最为常见的一种展示信息的形式&#xff0c;二次确认弹窗是其中最为经典的一种。当我们在React&#xff0c;Vue这种数据驱动视图的前端框架中渲染弹窗基本是固定的使用形式。 使用方式&#xff1a;创建新的弹窗组件&#xff0c;在需要弹窗的地方引用并…...

docker使用(一)生成,启动,更新(容器暂停,删除,再生成)

docker使用&#xff08;一&#xff09; 编写一个 Dockerfile构建镜像构建失败构建成功 运行镜像运行成功 修改代码后再次构建请不要直接进行构建&#xff0c;要将原有的旧容器删除或暂停停止成功删除成功再次构建且构建成功&#xff01; 要创建一个镜像&#xff0c;你可以按照以…...

用Qt自制一个小闹钟

小闹钟 功能 当按下启动按钮时&#xff0c;停止按钮可用&#xff0c;启动按钮不可用&#xff0c;闹钟无法设置&#xff0c;无法输入自定义内容 当按下停止按钮时&#xff0c;暂停播报&#xff0c;启动按钮可用&#xff0c;闹钟可以设置&#xff0c;可以输入自定义内容 .pro文…...

Vue2.0/Vue3.0使用xlsx+xlsx-style实现导出Excel文件

一、依赖导入 1、Vue2 Webpack构建的 npm i xlsx npm i xlsx-style npm i file-saver同时修改以下&#xff1a; 解决 Can’t resolve ‘./cptable’ in ‘…’ 的问题&#xff0c;在 vue.config.js 文件中加入该配置 module.exports {externals: {./cptable: var cptable}…...

【Kafka系列】(一)Kafka入门

有的时候博客内容会有变动&#xff0c;首发博客是最新的&#xff0c;其他博客地址可能会未同步,认准https://blog.zysicyj.top 首发博客地址 系列文章地址 Kafka是什么&#xff1f; 一句话概括&#xff1a;「Apache Kafka 是一款开源的消息引擎系统」 什么是消息引擎系统&#…...

外包干了2个月,技术退步明显了...

先说一下自己的情况&#xff0c;大专生&#xff0c;19年通过校招进入湖南某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年8月份&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试…...

python实现语音识别

1. 首先安装依赖库 pip install playsound # 该库用于播放音频文件 pip install speech_recognition # 该库用于语音识别 pip install PocketSphinx # 语音识别模块中只有sphinx支持离线的&#xff0c;使用该模块需单独安装 pip install pyttsx3 # 该库用于将文本转换为语音播…...

java八股文面试[多线程]——线程的状态

5种状态一般是针对传统的线程状态来说&#xff08;操作系统层面&#xff09; 6种状态&#xff1a;Java中给线程准备的 NEW&#xff1a;Thread对象被创建出来了&#xff0c;但是还没有执行start方法。 RUNNABLE&#xff1a;Thread对象调用了start方法&#xff0c;就为RUNNABLE状…...

Go学习[合集]

文章目录 Go学习-Day1Go学习-Day2标识符变量基础语法字符串类型类型转换string和其他基本类型转换其他类型转stringstring转其他类型 指针类型运算符标准IO分支语句 Go学习-Day3循环语句函数声明init函数匿名函数闭包defer Go学习-Day4函数值传递&#xff0c;引用传递常用的函数…...

代码随想录算法训练营第42天 | ● 01背包问题,你该了解这些! ● 01背包问题,你该了解这些! 滚动数组 ● 416. 分割等和子集

文章目录 前言一、01背包问题&#xff0c;你该了解这些&#xff01;二、01背包问题&#xff0c;你该了解这些&#xff01; 滚动数组三、416. 分割等和子集总结 前言 01背包 一、01背包问题&#xff0c;你该了解这些&#xff01; 确定dp数组以及下标的含义 对于背包问题&#x…...

解决DNS服务器未响应错误的方法

​当你将设备连接到家庭网络或具有互联网接入功能的Wi-Fi热点时,由于各种原因,互联网连接可能无法正常工作。本文中的说明适用于Windows 10、Windows 8和Windows 7。 无法连接到DNS服务器的原因 故障的一类与域名系统有关,域名系统是世界各地互联网提供商使用的分布式名称…...

SpringBoot的HandlerInterceptor拦截器使用方法

一、创建拦截器 通过实现HandlerInterceptor接口创建自己要使用的拦截器 import org.springframework.context.annotation.Configuration; import org.springframework.web.servlet.HandlerInterceptor; import org.springframework.web.servlet.ModelAndView; import javax.…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

门静脉高压——表现

一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构&#xff1a;由肠系膜上静脉和脾静脉汇合构成&#xff0c;是肝脏血液供应的主要来源。淤血后果&#xff1a;门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血&#xff0c;引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...