28_二叉树的最近公共祖先

简介: 28_二叉树的最近公共祖先

236.二叉树的最近公共祖先

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

百度百科中最近公共祖先的定义为:“对于有根树 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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // TreeNode left = null, right = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return root;
        if (p == root || q == root) {
            return root;//当前节点就是q和p的祖先节点
        }
        // 左
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 右
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 中
        if (left != null && right == null){
            return left;
        } else if (left == null && right != null) {
            return right;
        } else if (left == null && right == null){
            return null;
        } else {
            return root;  //找到了
        }
    }
}
相关文章
|
Java
规则引擎选型及应用
规则引擎具体执行可以分为接受数据输入,解释业务规则,根据业务规则做出业务决策几个过程。 使用规则引擎可以把复杂、冗余的业务规则同整个支撑系统分离开,做到架构的可复用移植。
25136 0
|
存储 Java 调度
开发踩坑记录之二:谨慎使用Spring中的@Scheduled注解
在一些业务场景中需要执行定时操作来完成一些周期性的任务,比如每隔一周删除一周前的某些历史数据以及定时进行某项检测任务等等。在日常开发中比较简单的实现方式就是使用Spring的@Scheduled(具体使用方法不再赘述)注解。但是在修改服务器时间时会导致定时任务不执行情况的发生,解决的办法是当修改服务器时间后,将服务进行重启就可以避免此现象的发生。本文将主要探讨服务器时间修改导致@Scheduled注解失效的原因,同时找到在修改服务器时间后不重启服务的情况下,定时任务仍然正常执行的方法。 @Scheduled失效原因分析 解析流程图 使用新的方法
开发踩坑记录之二:谨慎使用Spring中的@Scheduled注解
|
Linux
yum镜像源汇总
yum镜像源汇总
5461 0
|
11月前
|
机器学习/深度学习 算法 索引
YOLOv11改进 - 卷积Conv | 加权卷积wConv:无损替换标准卷积,增强空间建模与特征提取质量
本文提出加权卷积(wConv),通过引入距离感知的密度函数,自适应调整邻域像素权重,突破传统卷积等权局限。结合双优化器策略,在不增加参数量的前提下提升特征提取能力。集成于YOLOv11后显著降低损失、提高检测精度,适用于图像去噪等密集预测任务。
|
2月前
|
人工智能 安全 API
零门槛接入大模型、免费千万Tokens上手:阿里云百炼API‑Key申领、权限管控、多系统配置与示例代码教程
大模型服务平台百炼汇集多款主流大模型,覆盖文本对话、多模态识图、文生视频、Agent智能体、知识库RAG等丰富能力。新开通服务的账号会自动发放超7000万免费Tokens额度,每款标准模型分配100万免费Token,非常适合开发者做原型验证、学习调试业务逻辑。想要通过程序、第三方AI工具调用平台各类大模型能力,API‑Key是核心身份凭证,每一次接口请求都依靠该密钥完成身份鉴权,确定调用账号、可用模型以及计费抵扣规则。
867 0
|
2月前
|
存储 人工智能 开发框架
【新版】阿里云 无影云电脑 产品功能介绍及配置价格表
传统本地PC、物理工作站面临硬件迭代快、算力固定、数据分散难以管控、异地办公设备受限、AI智能体7×24小时持续运行硬件成本高等现实痛点。无影云电脑(Elastic Desktop Service,EDS)是托管式云上虚拟桌面服务,把完整计算机运行环境部署在云端算力底座,计算、存储全部运行在云端,本地终端只负责画面接收、键鼠输入输出,本地终端不会留存业务原始数据,实现数据不落地的安全办公模式。产品分为个人版、企业版两大产品线,覆盖个人学习办公、远程开发、图形设计渲染、企业批量办公、AI智能体云端工位、RPA自动化等多元场景,底层搭载自研ASP自适应流化协议,兼顾画面流畅度与网络弱网适配能力,配
629 0
|
3月前
|
存储 关系型数据库 MySQL
读写混合TPS差六倍,PostgreSQL与MySQL架构差异实测
从架构设计、索引实现、事务隔离、复制机制、运维体验五个维度深度对比PostgreSQL与MySQL,覆盖MySQL 9.0向量检索与PostgreSQL 17新特性,附权威基准数据和选型决策框架
|
4月前
|
人工智能 API 数据库
Kimi深夜突袭K3,2.8万亿参数超大水桶!直接跨入世界第一梯队!
老金我昨儿在网上瞎逛的时候,突然看到了Kimi K3的消息。 合计先打开官网看看开发者文档有没有啥信儿,结果刚打开官网,好家伙。。就看到已经上线了! ![Image](https://ucc.alicdn.com/pic/developer-ecology/p3shvhj26rigq_0488c34b2827443e9b77df8ee1e3a066.png) Kimi官网Chat窗口里已
|
3月前
|
人工智能 搜索推荐 测试技术
GEO行业科普:别拿SEO经验忽悠AI时代的新玩家
GEO(生成式引擎优化)是2024年才由普林斯顿大学正式命名的新兴领域,核心是让AI“理解、信任并引用”品牌内容,而非传统SEO的排名与点击。其逻辑迥异:重语义相关性、结构化标记、E-E-A-T可信度与跨平台一致性。2026年市场规模预计达286亿元,但真正落地率不足15%——所谓“十几年GEO经验”,多为SEO的伪服务经验。
|
人工智能 IDE 开发工具
从0到1彻底掌握Trae:手把手带你实战开发AI Chatbot,提升开发效率的必备指南!
Trae是字节跳动推出的一款免费的AI集成的开发环境,集成了Claude3.5与GPT-4o等主流AI模型,提供AI问答、智能代码生成、智能代码补全,多模态输入等功能。支持界面全中文化,为中文开发者提供了高效的开发体验
11931 11
从0到1彻底掌握Trae:手把手带你实战开发AI Chatbot,提升开发效率的必备指南!