原题
给定一个二叉二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例1：
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例2：
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
解法
思想
利用二叉搜索树的性质，两个节点p、q可以有两种分布情况：
1. 分别位于公共祖先的左、右子树。
2. 其中一个节点就是公共祖先，另一个节点位于子树上。
如此递归查找。
代码
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val>p.val && root.val>q.val) return lowestCommonAncestor(root.left, p, q);
if(root.val<p.val && root.val<q.val) return lowestCommonAncestor(root.right,p,q);
return root;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode235-%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91%e7%9a%84%e6%9c%80%e8%bf%91%e5%85%ac%e5%85%b1%e7%a5%96%e5%85%88/
相关推荐
-
leetcode74-搜索二维矩阵
原题 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。 示例...
-
leetcode841-钥匙和房间
原题 有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。 在形式上，对于每个房间 i 都有一...
-
leetcode706-设计哈希映射
原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说，你的设计应该包含以下的功能 put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更...
-
leetcode39-组合总和
原题 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates ...
-
leetcode1300-转变数组后最接近目标值的数组和
原题 给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 targe...
-
leetcode206-反转链表
原题 反转一个单链表。 示例： 输入： 1->2->3->4->5->NULL 输出： 5->4->3->2->1->NULL 进阶： 你可以迭代或递归地反转链表。你能否用两种方法...
-
leetcode14-最长公共前缀
原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “...
-
leetcode344-反转字符串
原题 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组char[]的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间...
-
leetcode150-逆波兰表达式求值
原题 根据逆波兰表示法，求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 说明： 整数除法只保留整数部分。 给定逆波兰...
-
leetcode456-132模式
原题 给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak <...