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

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param p int整型 
 * @param q int整型 
 * @return int整型
 */
function lowestCommonAncestor( root ,  p ,  q ) {
    // write code here
    //递归实现
    //1.空节点没有祖先
    if(!root){
        return;
    }
    //2.当p和q小于这个节点，那么这个公共祖先在左子树中
    if(p < root.val&& q < root.val){
        return lowestCommonAncestor(root.left,p,q)
    }else if(p > root.val&&q > root.val){
        //3.当p和q都大于这个节点，那么这个公共祖先再右子树中
        return lowestCommonAncestor(root.right,p,q)
    }else{
        //4.当他们其中一个>=或者<=，一个节点的时候，那么他们公共祖先就是该接待你
        return root.val
    }
}
module.exports = {
    lowestCommonAncestor : lowestCommonAncestor
};