leetcode236—二叉树的最近公共祖先(递归/深搜/理解)

简介: leetcode236—二叉树的最近公共祖先(递归/深搜/理解)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中:

最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”


深搜,找到就返回,判断此时是否左右子树分别含p,q(或者root本身是p或者q)。因为如果pq存在一个子树时(例如都在左子树中),可能左子树结点才是最近公共祖先。

画图,理解返回值的过程。


引用 k神 的递归解析,(主要还是自己画)

递归解析:

终止条件:

当越过叶节点,则直接返回 null ;

当 root 等于 p,q ,则直接返回 root ;

递推工作:

开启递归左子节点,返回值记为 left ;

开启递归右子节点,返回值记为 right ;

返回值: 根据 left 和 right ,可展开为四种情况;

当 left 和 right 同时为空 :说明 root 的左 / 右子树中都不包含 p,q ,返回 null ;

当left 和 right 同时不为空 :说明 p,q 分列在 root 的 异侧 (分别在 左 / 右子树),因此 root 为最近公共祖先,返回 root ;

当 left 为空 ,right 不为空 :p,q 都不在 root 的左子树中,直接返回 right 。具体可分为两种情况:p,q 其中一个在 root 的 右子树 中,此时 right 指向 p(假设为p );

p,q 两节点都在 root 的 右子树 中,此时的 right 指向 最近公共祖先节点 ;

当 left 不为空 , right 为空 :与情况 3. 同理;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* dfs(struct TreeNode* root,struct TreeNode* p,struct TreeNode* q)
{
    struct TreeNode* l,* r;
    if(root == NULL)
        return NULL;
    if(root == p || root == q)
        return root;
    l = dfs(root->left,p,q);
    r = dfs(root->right,p,q);
    if(l != NULL && r != NULL)
        return root;
    else if(l == NULL && r!= NULL)
        return r;
    else
        return l;
}
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    //已知层序遍历的数组 真笨蛋 看错题了 想了半个点
    return dfs(root,p,q);
}
相关文章
|
1月前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
17 1
|
1月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
18 0
|
1月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
14 0
|
1月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
16 0
|
1月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
12 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
56 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
113 2
|
18天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
16 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口