这题让求二叉搜索树的最近公共祖先,而二叉搜索树的特点就是左子树的所有节点都小 于当前节点,右子树的所有节点都大于当前节点,并且每棵子树都具有上述特点, 所以 这题就好办了,从根节点开始遍历
    如果两个节点值都小于根节点,说明他们都在根节点的左子树上,我们往左子树上找
    如果两个节点值都大于根节点,说明他们都在根节点的右子树上,我们往右子树上找
    如果一个节点值大于根节点,一个节点值小于根节点,说明他们他们一个在根节点 的左子树上一个在根节点的右子树上,那么根节点就是他们的最近公共祖先节点。

    画个图看一下,比如要找0和5的最近公共祖先节点,如下图所示
    image.png
    image.png

    1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    2. // 如果root的值大于p、q的值,说明最近公共祖先在左子树
    3. if (root.val > p.val && root.val > q.val) {
    4. return lowestCommonAncestor(root.left, p, q);
    5. }
    6. // 如果root的值小于p、q的值,说明最近公共祖先在左子树
    7. if (root.val < p.val && root.val < q.val) {
    8. return lowestCommonAncestor(root.right, p, q);
    9. }
    10. // 如果p、q的值分别在root的左右子树中,那root就是最近公共祖先
    11. return root;
    12. }