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;  //找到了
        }
    }
}
相关文章
|
12月前
|
存储 安全 Java
深入理解Java中的FutureTask:用法和原理
【10月更文挑战第28天】`FutureTask` 是 Java 中 `java.util.concurrent` 包下的一个类,实现了 `RunnableFuture` 接口,支持异步计算和结果获取。它可以作为 `Runnable` 被线程执行,同时通过 `Future` 接口获取计算结果。`FutureTask` 可以基于 `Callable` 或 `Runnable` 创建,常用于多线程环境中执行耗时任务,避免阻塞主线程。任务结果可通过 `get` 方法获取,支持阻塞和非阻塞方式。内部使用 AQS 实现同步机制,确保线程安全。
1117 3
|
人工智能
用AI人模拟社会学实验,居然成功了?斯坦福、NYU用GPT-4模仿人类,准确度惊人!
斯坦福大学和纽约大学的研究团队利用GPT-4模型成功模拟了人类在社交互动中的行为模式,实验结果显示AI能以惊人准确度模仿人类对话,甚至在在线论坛和社交媒体上与真人难以区分。这一突破不仅展示了AI在社会学研究中的巨大潜力,还引发了对AI伦理和透明度的深入探讨。尽管存在一些局限性和挑战,这项研究为未来社会学实验提供了新工具和方法。[论文地址:https://docsend.com/view/qeeccuggec56k9hd]
509 2
el-tree饿了么elementUI tree树结构插件设置全部展开折叠
el-tree饿了么elementUI tree树结构插件设置全部展开折叠
|
存储 C++
经典的QVariant设计之道
经典的QVariant设计之道
|
存储 NoSQL Shell
InfluxDB的存储引擎演化过程
InfluxDB的存储引擎从LSM Tree,到mmap B+ Tree,再到TSM Tree。
6925 0
|
缓存 小程序 API
微信小程序-每个页面中的Page函数
微信小程序可有意思了
830 0
|
Java API
Java中BigDecimal详解及应用
BigDecimal用来对超过16位有效位的数进行精确的运算。双精度浮点型变量double可以处理16位有效数,但在实际应用中,可能需要对更大或者更小的数进行运算和处理。一般情况下,对于那些不需要准确计算精度的数字,我们可以直接使用Float和Double处理,但是Double.valueOf(String) 和Float.valueOf(String)会丢失精度。所以在开发中,如果你所做的业务跟财务相关需要精确计算的结果,那必须使用BigDecimal类来操作啦!
504 2
Java中BigDecimal详解及应用
|
弹性计算 固态存储 数据可视化
2023阿里云服务器常用配置最新优惠价格整理对照表
2023阿里云服务器常用配置最新优惠价格整理对照表,阿里云服务器分为云服务器ECS和轻量应用服务器,云服务器s6公网带宽可选1M到5M,系统盘40G起可选高效云盘、SSD云盘或ESSD云盘,1核1G配置19.17元3个月、306.72元一年,1核2G优惠价26.46元3个月、423.36元一年,2核4G配置42.66元3个月,2核8G配置58.86元3个月,4核8G 75.06元3个月,8核16G 139.86元3个月,还有4核16G、8核32G多配置可选。不只是云服务器ECS共享型s6实例,ECS计算型c6、通用型g6、内存型r6、云服务器u1
574 0
2023阿里云服务器常用配置最新优惠价格整理对照表
|
弹性计算 大数据 测试技术
阿里云服务器租用价格表-2023最新(附明细报价)
阿里云服务器租用价格表-2023最新(附明细报价),阿里云轻量应用服务器2核2G3M带宽轻量服务器一年108元,2核4G4M带宽轻量服务器一年297.98元12个月
1493 0
|
弹性计算 人工智能 调度