题解 | 二叉搜索树的最近公共祖先

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        if(root==null) return -1;
        if(root.val==p || root.val==q) return root.val;

        if(root.val<p&&root.val>q) return root.val;
        if(root.val>p&&root.val<q) return root.val;

        if(root.val>p&&root.val>q){
            return lowestCommonAncestor(root.left,p,q);
        }

        
        return lowestCommonAncestor(root.right,p,q);
       

        
    }
}

这个问题采用递归的方法来解决，由于是二叉排序树，所以根据当前节点与p,q的大小关系寻找。分为下面几种条件：

1 根节点为null, 返回-1；

2 根节点的值等于p或者q,返回根节点的值；

3 根节点的值介于p,q 之间，返回根节点的值；

4 根节点的值大于p,q 递归往左子树找

5 根节点的值小于p,q 递归往右子树找