当前位置:网站首页>leetcode:236. 二叉树的最近公共祖先
leetcode:236. 二叉树的最近公共祖先
2022-07-06 15:53:00 【uncle_ll】
236. 二叉树的最近公共祖先
来源:力扣(LeetCode)
链接: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3:
输入:root = [1,2], p = 1, q = 2
输出:1
提示:
- 树中节点数目在范围 [2, 1 0 5 10^5 105] 内。
- − 1 0 9 -10^9 −109 <= Node.val <= 1 0 9 10^9 109
- 所有 Node.val 互不相同 。
- p != q
- p 和 q 均存在于给定的二叉树中。
解法
- 递归: 先从根节点开始判断,如果根节点为空,或者某个查找元素为根节点,直接返回根节点;然后递归查找左子树,右子树,如果两个子树查找结果都不为空,表明p,q待查找的两个元素与左子树的根节点或者右子树的根节点相同,则二者的公共节点为该树的根节点;如果有一个子树的查找为空,则返回另外一个子树的查找结果;
代码实现
递归
python实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return root
if root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right: # 二个子树的查找结果都不为空,说明拍,
return root
return left if left else right
c++实现
/** * 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)
return root;
if (p == root || q == root)
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != nullptr && right != nullptr)
return root;
return left != nullptr ? left : right;
}
};
复杂度分析
- 时间复杂度: O ( N ) O(N) O(N)
- 空间复杂度: O ( N ) O(N) O(N)
边栏推荐
- (shuttle) navigation return interception: willpopscope
- Why are some people still poor and living at the bottom of society even though they have been working hard?
- What can be done for traffic safety?
- (flutter2) as import old project error: inheritfromwidgetofexacttype
- COSCon'22 社区召集令来啦!Open the World,邀请所有社区一起拥抱开源,打开新世界~
- 同一个作业有两个source,同一链接不同数据库账号,为何第二个链接查出来的数据库列表是第一个账号的
- CRMEB 商城系统如何助力营销?
- Stop saying that microservices can solve all problems
- Huawei cloud gaussdb (for redis) unveils issue 21: using Gauss redis to achieve secondary indexing
- Redis persistence mechanism
猜你喜欢
On file uploading of network security
今日睡眠质量记录78分
Flutter life cycle
Implementation steps of mysql start log in docker
Bipartite graph determination
每人每年最高500万经费!选人不选项目,专注基础科研,科学家主导腾讯出资的「新基石」启动申报...
传统企业要为 Web3 和去中心化做的 11 个准备
若依请求url中带有jsessionid的解决办法
云原生(三十二) | Kubernetes篇之平台存储系统介绍
MySQL connected vscode successfully, but this error is reported
随机推荐
AcWing 4300. Two operations (minimum number of BFS searches)
不要再说微服务可以解决一切问题了
Detailed explanation of regular expression (regexp) in MySQL
Spark Tuning (II): UDF reduces joins and judgments
(1) Chang'an chain learning notes - start Chang'an chain
Graphite document: four countermeasures to solve the problem of enterprise document information security
MySQL connected vscode successfully, but this error is reported
Flutter life cycle
MySQL实现字段分割一行转多行的示例代码
Wu Enda 2022 machine learning course evaluation is coming!
The worse the AI performance, the higher the bonus? Doctor of New York University offered a reward for the task of making the big model perform poorly
基础图表解读“东方甄选”爆火出圈数据
Example code of MySQL split string as query condition
(shuttle) navigation return interception: willpopscope
电脑重装系统u盘文件被隐藏要怎么找出来
Thinkphp5 multi table associative query method join queries two database tables, and the query results are spliced and returned
请问oracle-cdc用JsonDebeziumDeserializationSchema反序列化
Should the jar package of MySQL CDC be placed in different places in the Flink running mode?
[unity] upgraded version · Excel data analysis, automatically create corresponding C classes, automatically create scriptableobject generation classes, and automatically serialize asset files
CRMEB 商城系统如何助力营销?