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

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

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

1. p,q 都比 root 节点值小,所以 p,q 都在左子树.
2. p,q 都比 root 节点值大,所以 p,q 都在右子树.
3. 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;
    }
}