【leetcode-235】二叉搜索树的最近公共祖先

简介: 看到二叉树的题目,首先要想到递归,因为大多数的二叉树题目都是可以通过递归来解决的,再看这是一个二叉搜索树,立马就想到二叉搜索树的特质,左子树上所有节点的值都小于根节点的值,右子树上所有节点的值都大于根节点的值,它的左右子树也分别为二叉搜索树.那我们怎么能利用这个性质呢?

题目:



思路:


看到二叉树的题目,首先要想到递归,因为大多数的二叉树题目都是可以通过递归来解决的,再看这是一个二叉搜索树,立马就想到二叉搜索树的特质,左子树上所有节点的值都小于根节点的值,右子树上所有节点的值都大于根节点的值,它的左右子树也分别为二叉搜索树.那我们怎么能利用这个性质呢?


可以分三种情况来分析问题:


p,q 都比 root 节点值小,所以 p,q 都在左子树.

p,q 都比 root 节点值大,所以 p,q 都在右子树.

p,q 一个比 root 节点值小,一个比 root 节点值大,也就是 p,q 分布在 root 节点的左右子树两边.或者 p,q 其中一个节点就是 root 节点,此时都应该直接返回 root.

代码:

分析完所有的情况后,代码就比较好写了.根据上面的思路,解题代码如下所示:


class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
        if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}


提交结果:


相关文章
|
2月前
【LeetCode 45】701.二叉搜索树中的插入操作
【LeetCode 45】701.二叉搜索树中的插入操作
10 1
|
2月前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
18 1
|
2月前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
40 0
|
2月前
【LeetCode 47】669.修剪二叉搜索树
【LeetCode 47】669.修剪二叉搜索树
10 0
|
2月前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
19 0
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
20 0
|
2月前
【LeetCode 42】501.二叉搜索树中的众数
【LeetCode 42】501.二叉搜索树中的众数
10 0
|
2月前
【LeetCode 41】530.二叉搜索树的最小绝对差
【LeetCode 41】530.二叉搜索树的最小绝对差
11 0
|
2月前
【LeetCode 40】98.验证二叉搜索树
【LeetCode 40】98.验证二叉搜索树
13 0
|
2月前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
16 0