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

[JesseZhao1990]

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if(root === null) return null;
    // 如果两个节点的值全部在节点的右侧，则说明不是最近的节点，需要进一步向右搜索
    if(p.val > root.val && q.val >root.val){
        return lowestCommonAncestor(root.right,p,q);
    }
    // 如果两个节点的值全部在节点的左侧，则说明不是最近的节点，需要进一步向左搜索
    if(p.val < root.val && q.val < root.val){
        return lowestCommonAncestor(root.left,p,q);
    }
    // 如果不满足上边的两个条件，说明p和q分布在节点的两侧，此时找到最近的节点
    return root;
    
};

解题思路：

如果p和q分布在某个节点的两侧，说明此节点是最近的公共祖先

leetcode原题地址：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/