235. Lowest Common Ancestor of a Binary Search Tree

题干简述：

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

Wiki 中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”。

解题思路

二叉检索树的特殊性质本次就不再阐述了，不了解的同学可以参考我之前的题解，搭配 google 食用。题干中给出的最近公共祖先（LCA）wiki 定义讲的也很清楚，需要注意的是，“ x 的深度尽可能大”翻译过来也就是离 p, q 尽可能的近。如果不考虑 BST 的特殊性质，此题通过递归，也是一样可以求解。每次递归时，判断当前节点的值，是否在 [p, q] 内；若是，直接返回；若否，继续对其左右子节点进行递归。但是，由于 BST 其左（右）子树的值必然小于（大于）其自身。因此，我们在判断当前节点是在 [p, q] 区间的左侧还是右侧后，可以只对其左（右）节点进行遍历。

题解

/**
 * 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.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
    if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
    return root;
};

Q.E.D.

Take it easy