当前位置:网站首页>leetcode刷题:二叉树25(二叉搜索树的最近公共祖先)
leetcode刷题:二叉树25(二叉搜索树的最近公共祖先)
2022-07-07 10:30:00 【涛涛英语学不进去】
235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 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, 因为根据定义最近公共祖先节点可以为节点本身。
本题用我上一节的通用做法也能做,不过是二叉搜索树,有序,可以针对性质来做。 性质:有序(非递减)
package com.programmercarl.tree;
/** * @ClassName BstLowestCommonAncestor * @Descriotion TODO * @Author nitaotao * @Date 2022/7/6 12:36 * @Version 1.0 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/ * 235. 二叉搜索树的最近公共祖先 **/
public class BstLowestCommonAncestor {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//因为是有序的,只要找到最接近两个元素的结点
// 模板结点在当前结点左边
if (root.val > p.val && root.val > q.val) {
root = root.left;
} else if (root.val < p.val && root.val < q.val) {
root = root.right;
} else {
//root在两个结点位置之间了,是闭区间。而且是 [p,q]的闭区间,不是 p 就是 q
//因为是一步步位移的,所以是临界点
return root;
}
return lowestCommonAncestor(root, p, q);
}
}
边栏推荐
- 小红书微服务框架及治理等云原生业务架构演进案例
- SQL lab 11~20 summary (subsequent continuous update) contains the solution that Firefox can't catch local packages after 18 levels
- H3C HCl MPLS layer 2 dedicated line experiment
- Is it safe to open an account in Ping An Securities mobile bank?
- [play RT thread] RT thread Studio - key control motor forward and reverse rotation, buzzer
- 即刻报名|飞桨黑客马拉松第三期盛夏登场,等你挑战
- 数据库系统原理与应用教程(008)—— 数据库相关概念练习题
- 源代码防泄密中的技术区别再哪里
- Visual studio 2019 (localdb) \mssqllocaldb SQL Server 2014 database version is 852 and cannot be opened. This server supports version 782 and earlier
- TypeScript 接口继承
猜你喜欢
Hi3516 full system type burning tutorial
Unity map auto match material tool map auto add to shader tool shader match map tool map made by substance painter auto match shader tool
File upload vulnerability - upload labs (1~2)
(to be deleted later) yyds, paid academic resources, please keep a low profile!
BGP actual network configuration
Tutorial on principles and applications of database system (009) -- conceptual model and data model
About sqli lab less-15 using or instead of and parsing
问题:先后键入字符串和字符,结果发生冲突
消息队列消息丢失和消息重复发送的处理策略
【深度学习】图像多标签分类任务,百度PaddleClas
随机推荐
Decrypt gd32 MCU product family, how to choose the development board?
wallys/Qualcomm IPQ8072A networking SBC supports dual 10GbE, WiFi 6
Xiaohongshu microservice framework and governance and other cloud native business architecture evolution cases
BGP third experiment report
What are the top-level domain names? How is it classified?
OSPF exercise Report
[Q&A]AttributeError: module ‘signal‘ has no attribute ‘SIGALRM‘
@Bean与@Component用在同一个类上,会怎么样?
111. Network security penetration test - [privilege escalation 9] - [windows 2008 R2 kernel overflow privilege escalation]
Several methods of checking JS to judge empty objects
Customize the web service configuration file
数据库系统原理与应用教程(011)—— 关系数据库
<No. 8> 1816. 截断句子 (简单)
Upgrade from a tool to a solution, and the new site with praise points to new value
The IDM server response shows that you do not have permission to download the solution tutorial
Financial data acquisition (III) when a crawler encounters a web page that needs to scroll with the mouse wheel to refresh the data (nanny level tutorial)
[play RT thread] RT thread Studio - key control motor forward and reverse rotation, buzzer
Is it safe to open an account in Ping An Securities mobile bank?
Tutorial on the principle and application of database system (008) -- exercises on database related concepts
什么是ESP/MSR 分区,如何建立ESP/MSR 分区