AlgoPressAppearance
0235-二叉搜索树的最近公共祖先
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 都小于 root.val 那么说明他们的最近公共祖先在左子树中
- 如果 p,q 都大于 root.val 说明他们的最近公共祖先都在右子树中。 (如果 p,q 一个小于 root.val 一个 大于 root.val 那么说明 root 就是最近公共祖先) (如果一个等于 root.val 另一个大于/小于公共祖先 返回 root ) 其实以上两种情况，都是返回 root，因此我们只需要处理最上面1,2两种情况
参考代码
csharp
public class Solution {
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || p == null || q == null){
return null;
}
TreeNode leftNode = p.val < q.val ? p : q;
TreeNode rightNode = p.val > q.val ? p : q;
if(leftNode.val < root.val && rightNode.val < root.val){
return LowestCommonAncestor(root.left, p, q);
}
if(leftNode.val > root.val && rightNode.val > root.val){
return LowestCommonAncestor(root.right, p, q);
}
return root;
}
}
参考代码【简化】
不需要吧 p,q拆开比较
csharp
public class Solution {
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}
if(p.val < root.val && q.val < root.val){
return LowestCommonAncestor(root.left, p, q);
}
else if(p.val > root.val && q.val > root.val){
return LowestCommonAncestor(root.right, p, q);
}
else{
return root;
}
}
}