当前位置:网站首页>Leetcode 236. 二叉树的最近公共祖先
Leetcode 236. 二叉树的最近公共祖先
2022-08-09 22:05:00 【LuZhouShiLi】
Leetcode 236. 二叉树的最近公共祖先
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
思路
递归出口
- 当越过叶子节点,直接返回null
- 当root等于p,q,直接返回root
递归工作
- 递归左子树
- 递归右子树
- 判断左子树和右子树是否为空
返回值
- 左右子树都不为空,说明左右子树都不包含p,q,返回null
- 当左右子树同时不为空,直接返回root
- 当左右子树有一个为空,另一个不为空,返回不为空的那个
代码
/** * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr || root == p || root == q)
{
return root;
}
// 递归左子树
TreeNode *l = lowestCommonAncestor(root->left,p,q);
// 递归右子树
TreeNode *r = lowestCommonAncestor(root->right,p,q);
if(l == nullptr)
{
// 左子树为空 p q 在右子树中
return r;
}
if(r == nullptr)
{
return l;// 右子树为空 pq 在左子树中
}
return root;
}
};
边栏推荐
- 【软考 系统架构设计师】案例分析⑤ 质量属性和架构评估
- R语言修改dataframe数据列的名称:使用dplyr包的rename函数修改列名、使用colnmaes函数修改列名、在数据筛选的时候重命名列名
- R语言使用mean函数计算样本(观测)数据中指定变量的相对频数:计算时间序列数据中大于前一个观测值的观测值所占的比例总体的比例
- 数字与中文大写数字互转(5千万亿亿亿亿以上的数字也支持转换)
- leetcode:325. 和等于k的最长子数组长度
- 17-GuliMall 搭建虚拟域名访问环境
- NodeJS使用JWT
- 【技术分享】SLA(服务等级协议)原理与配置
- VR全景拍摄如何拍摄?如何使用拍摄器材?
- 少儿编程 电子学会图形化编程等级考试Scratch三级真题解析(判断题)2022年6月
猜你喜欢
Flask's routing (app.route) detailed
用PLSQL导出Oracle一个表
leetcode brush questions diary Calculate the number of elements on the right that is less than the current element
【Burning】It's time to show your true strength!Understand the technical highlights of the 2022 Huawei Developer Competition in one article
数字与中文大写数字互转(5千万亿亿亿亿以上的数字也支持转换)
Kubernetes Service对象
three.js镂空圆球拖拽变形js特效
注意力引导网络用于视网膜图像分割
How do task flow executors work?
Qt message mechanism and events
随机推荐
[Microservice~Nacos] Nacos service provider and service consumer
Evolution of MLOps
Space not freed after TRUNCATE table
Cesium渐变色3dtiles白模(视频)
量化交易接口系统有哪些稳定性?
(转)字符集编码标识符,数字表示字符编码
leetcode 38. 外观数列
大型分布式存储方案MinIO介绍,看完你就懂了!
HUAWEI CLOUD escorts the whole process of "Wandering Ark" for the first time, creating a popular brand
Flutter 绘制美不胜收的光影流动效果
【技术分享】SLA(服务等级协议)原理与配置
web 面试高频考点 —— 性能优化篇(手写防抖、手写节流、XXS攻击、XSRF攻击)
C. Mere Array
Core Data浅谈系列之五 : 在UITableView中展示
setter与getter访问器属性——数据驱动显示
Users should clearly know that quantitative trading is not a simple procedure
R语言将列表数据转化为向量数据(使用unlist函数将列表数据转化为向量数据)
Analyses the development status quo of stock trading
Postgresql源码(68)virtualxid锁的原理和应用场景
C. Omkar and Baseball