1、前言
题目描述
2、思路
二叉搜索树的最近公共祖先和二叉树的不一样，比二叉树的要简单一点。
二叉搜索树的公共祖先有个特性，就是祖先的值一定在两个节点中间。所以 root 的值比 p、q 都大，那么说明 p、q 都在 root 的左子树；如果 root 的值比 p、q 都小，那么说明 p、q 都在 root 的右子树。否则，直接返回 root，它一定是最近公共祖先。
3、代码
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;
}
}
网友评论