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

import java.util.*;

public class Solution {

public int lowestCommonAncestor (TreeNode root, int p, int q) {
    // write code here
    /*
        此题要根据二叉搜索树的特点来做
        已知二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
        若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
    */
    int mid = root.val;
    /*
        这里有两种情况，可以直接返回当前节点的值
        1. 当p或q等于当前节点值
        2. p在节点值左边，q在节点值右边
    */
    
    if(p==mid || q==mid || (p<mid&&mid<q))
        return mid;
    if(p<mid&&q<mid)
        //p和q都小于当前节点值，所以最近公共祖先在左子树
        return lowestCommonAncestor(root.left,p,q);
    else 
        //p和q都大于当前节点值，所以最近公共祖先在右子树
        return lowestCommonAncestor(root.right,p,q);
}

}