当前位置:网站首页>Leetcode 235. 二叉搜索树的最近公共祖先
Leetcode 235. 二叉搜索树的最近公共祖先
2022-08-09 22:05:00 【LuZhouShiLi】
Leetcode 235. 二叉搜索树的最近公共祖先
题目
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
思路
- 确定递归函数返回值以及参数:参数就是当前节点,以及两个节点p,q
- 终止条件,遇到空值 直接返回即可
- 遍历二叉搜索树的时候就是寻找区间[p->val,q->val] 如果p->val > cur->val, 同时q->val > cur->val,那么遍历右子树,反之遍历左子树。
代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
TreeNode* traversal(TreeNode* cur,TreeNode *p,TreeNode *q)
{
if(cur == NULL)
{
return cur;
}
if(cur->val > p->val && cur->val > q->val)
{
// 递归左子树
TreeNode* left = traversal(cur->left,p,q);
if(left != NULL)
{
return left;
}
}
if(cur->val < p->val && cur->val < q->val)
{
// 递归右子树
TreeNode* right = traversal(cur->right,p,q);
if(right != NULL)
{
return right;
}
}
return cur;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return traversal(root,p,q);
}
};
边栏推荐
- Qt message mechanism and events
- 如何坚持使用程序化系统?
- Liver all night to write a thirty thousand - word all the commands the SQL database, function, speaks clearly explain operators, content is rich, proposal collection + 3 even high praise!
- FileZilla搭建FTP服务器图解教程
- OFDM 十六讲 7 - Inter-Symbol-Interference
- R语言拟合ARIMA模型并使用拟合模型进行预测推理:使用forecast函数计算ARIMA模型未来值(包含时间点、预测值、两个置信区间)
- pip 离线到内网安装包
- C. Omkar and Baseball
- 2022年中国第三方证券APP创新专题分析
- Users should clearly know that quantitative trading is not a simple procedure
猜你喜欢
随机推荐
R语言修改dataframe数据列的名称:使用dplyr包的rename函数修改列名、使用colnmaes函数修改列名、在数据筛选的时候重命名列名
R语言使用mean函数计算样本(观测)数据中指定变量的相对频数:计算时间序列数据中大于前一个观测值的观测值所占的比例总体的比例
Liver all night to write a thirty thousand - word all the commands the SQL database, function, speaks clearly explain operators, content is rich, proposal collection + 3 even high praise!
[WeChat applet development (8)] Summary of audio background music playback problems
The 2022-8-9 sixth group of input and output streams
leetcode:321. 拼接最大数
你的 Link Button 能让用户选择新页面打开吗?
ArrayList 和 LinkedList 区别
(转)FreeType字体位图属性
都在说云原生,那云原生到底是什么?
&&、||、&、|
反射机制篇
第十七期八股文巴拉巴拉说(数据库篇)
浅析量股票化交易的发展现状
Postgresql源码(68)virtualxid锁的原理和应用场景
Transfer Learning & Kemin Initialization
pip 离线到内网安装包
Bi Sheng Compiler Optimization: Lazy Code Motion
电脑系统重装后怎么用打印机扫描出文件?
Analyze the Add() method in Fragment management from the source code