当前位置:网站首页>【日常训练--腾讯精选50】235. 二叉搜索树的最近公共祖先
【日常训练--腾讯精选50】235. 二叉搜索树的最近公共祖先
2022-07-07 00:03:00 【Puppet__】
题目
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 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 为不同节点且均存在于给定的二叉搜索树中。
代码
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
// 同时找到达p、q的路径,找两个路径的分岔点,充分利用二叉搜索树的性质
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode ansNode = root;
while(true){
if(p.val < ansNode.val && q.val < ansNode.val){
ansNode = ansNode.left;
}
else if(p.val > ansNode.val && q.val > ansNode.val){
ansNode = ansNode.right;
}
// 路径分叉了,该点为最近公共祖先
else{
break;
}
}
return ansNode;
}
}
边栏推荐
- Batch size setting skills
- Paper reading [open book video captioning with retrieve copy generate network]
- Five core elements of architecture design
- 淘宝商品详情页API接口、淘宝商品列表API接口,淘宝商品销量API接口,淘宝APP详情API接口,淘宝详情API接口
- Leetcode: maximum number of "balloons"
- 什么是依赖注入(DI)
- 消息队列:重复消息如何处理?
- JVM (19) -- bytecode and class loading (4) -- talk about class loader again
- Paper reading [MM21 pre training for video understanding challenge:video captioning with pre training techniqu]
- Introduction to distributed transactions
猜你喜欢
[paper reading] semi supervised left atrium segmentation with mutual consistency training
Zero sequence aperture of leakage relay jolx-gs62 Φ one hundred
毕业之后才知道的——知网查重原理以及降重举例
[JS component] custom select
Leakage relay jelr-250fg
R language [logic control] [mathematical operation]
Unity keeps the camera behind and above the player
Modes of optical fiber - single mode and multimode
Web architecture design process
[reading of the paper] a multi branch hybrid transformer network for channel terminal cell segmentation
随机推荐
什么是依赖注入(DI)
Flinksql 读写pgsql
纪念下,我从CSDN搬家到博客园啦!
三级菜单数据实现,实现嵌套三级菜单数据
nodejs获取客户端ip
What are the common message queues?
Leetcode: maximum number of "balloons"
拼多多商品详情接口、拼多多商品基本信息、拼多多商品属性接口
Paper reading [open book video captioning with retrieve copy generate network]
论文阅读【MM21 Pre-training for Video Understanding Challenge:Video Captioning with Pretraining Techniqu】
SQLSTATE[HY000][1130] Host ‘host. docker. internal‘ is not allowed to connect to this MySQL server
集群、分布式、微服务的区别和介绍
力扣102题:二叉树的层序遍历
ssm框架的简单案例
The year of the tiger is coming. Come and make a wish. I heard that the wish will come true
数据中心为什么需要一套基础设施可视化管理系统
SAP ABAP BDC(批量数据通信)-018
sql查询:将下一行减去上一行,并做相应的计算
判断文件是否为DICOM文件
How to get free traffic in pinduoduo new store and what links need to be optimized in order to effectively improve the free traffic in the store