当前位置:网站首页>剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
2022-07-04 22:20:00 【LuZhouShiLi】
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
题目
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
思路
- 当p,q都在root的右子树中,则遍历root.right
- 当p,q都在root的左子树,则遍历root.left
- 当p,q在root两边,说明找到了最近公共祖先
代码
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(root != null)
{
if(root.val < p.val && root.val < q.val)
{
// 字节点都比root值要小 说明pq在左子树 遍历左子树
root = root.right;
}
else if(root.val > p.val && root.val > q.val)
{
root = root.left;
}
else{
break;// p q在root左右两侧 说明root就是最近公共祖先 直接跳出
}
}
return root;
}
}
边栏推荐
- Lost in the lock world of MySQL
- 制作条形码的手机App推荐
- Persistence mechanism of redis
- Introducing QA into the software development lifecycle is the best practice that engineers should follow
- 环境加密技术解析
- 攻防世界 misc 进阶区 2017_Dating_in_Singapore
- 攻防世界 misc 高手进阶区 a_good_idea
- 攻防世界 MISC 进阶区 Erik-Baleog-and-Olaf
- Google Earth Engine(GEE)——Tasks升级,实现RUN ALL可以一键下载任务类型中的所有影像
- Li Kou 98: verify binary search tree
猜你喜欢
攻防世界 MISC 进阶区 3-11
Locust性能测试 —— 环境搭建及使用
The sandbox has reached a cooperation with digital Hollywood to accelerate the economic development of creators through human resource development
[the 2023 autumn recruitment of MIHA tour] open [the only exclusive internal push code of school recruitment eytuc]
Introducing QA into the software development lifecycle is the best practice that engineers should follow
Business is too busy. Is there really no reason to have time for automation?
Redis sentinel simply looks at the trade-offs between distributed high availability and consistency
串口数据帧
质量体系建设之路的分分合合
MySQL Architecture - user rights and management
随机推荐
Force buckle 2_ 1480. Dynamic sum of one-dimensional array
Gnawing down the big bone - sorting (II)
The new version judges the code of PC and mobile terminal, the mobile terminal jumps to the mobile terminal, and the PC jumps to the latest valid code of PC terminal
嵌入式开发:技巧和窍门——提高嵌入式软件代码质量的7个技巧
Analysis of environmental encryption technology
Persistence mechanism of redis
[acwing] solution of the 58th weekly match
Li Kou 98: verify binary search tree
[the 2023 autumn recruitment of MIHA tour] open [the only exclusive internal push code of school recruitment eytuc]
PostgreSQL server programming aggregation and grouping
页面关闭前,如何发送一个可靠请求
Naacl-22 | introduce the setting of migration learning on the prompt based text generation task
Test will: bug classification and promotion solution
测试必会:BUG的分类及推进解决
Shell script implements application service log warehousing MySQL
UML diagram memory skills
Locust性能测试 —— 环境搭建及使用
Close system call analysis - Performance Optimization
攻防世界 MISC 进阶区 hong
短视频系统源码,点击屏幕空白处键盘不自动收起