Java实现 LeetCode 236 二叉树的最近公共祖先
2023-09-14 08:58:06 时间
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 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。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null)
return right;
if(right == null)
return left;
return root;
}
}
相关文章
- 在java中print和println_JAVA命令行参数
- java除法保留两位小数_JAVA除法保留小数点后两位的两种方法
- java启动器_JAVA基础:Java 启动器如何查找类
- c语言与java哪个更好_c语言和java哪个好?[通俗易懂]
- java运行机制是什么_JAVA运行机制
- java redis锁_Java中Redis锁的实现[通俗易懂]
- java基本数据类型 think in java_Think in Java(一):Java基础[通俗易懂]
- JWT(java web token)
- 【说站】java动态代理的原理
- java事务_Java 事务详解[通俗易懂]
- Java-Response实现重定向
- Java学习-如何编译适配java版本的jar包
- java接入腾讯云人脸识别服务
- Java 实现将 数据库字段 转为Java实体类字段,就是转为驼峰命名
- Java 在使用迭代器迭代集合的过程中的注意事项详解编程语言
- Porting .Net RSA xml keys to Java详解编程语言
- Java之创建对象>7.Avoid finalizers详解编程语言
- MySQL与Java的无缝互联(java与mysql连接)
- java打开windows系统的浏览器详解编程语言
- 技术的融合突破极限:Java与Redis的技术融合(java与redis)
- 运行Linux中定时运行Java程序的实用方法(linux定时java)
- 使用Java程序执行Linux指令:实现自动化操作(java执行linux命令)
- 的应用Java在Oracle数据库中的重要性及应用(java在oracle里)
- 两种php调用Java对象的方法
- Java基于Runtime调用外部程序出现阻塞的解决方法