描述

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

1. 对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
2. 二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
3. 所有节点的值都是唯一的。
4. p、q 为不同节点且均存在于给定的二叉搜索树中。

数据范围: 3<=节点总数<=10000 0<=节点值<=10000

链接

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

示例

输入：{7,1,12,0,4,11,14,#,#,3,5},1,12
返回值：7
说明：节点1 和 节点12的最近公共祖先是7  

输入：{7,1,12,0,4,11,14,#,#,3,5},12,11
返回值：12
说明：因为一个节点也可以是它自己的祖先.所以输出12

题解

知识点：二叉搜索树

二叉搜索树是一种特殊的二叉树，它的每个节点值大于它的左子节点，且大于全部左子树的节点值，小于它右子节点，且小于全部右子树的节点值。因此二叉搜索树一定程度上算是一种排序结构。

思路：

二叉搜索树没有相同值的节点，因此分别从根节点往下利用二叉搜索树较大的数在右子树，较小的数在左子树，可以轻松找到p、q：

直接得到从根节点到两个目标节点的路径，这样我们利用路径就可以找到最近公共祖先。

具体做法：

step 1：根据二叉搜索树的性质，从根节点开始查找目标节点，当前节点比目标小则进入右子树，当前节点比目标大则进入左子树，直到找到目标节点。这个过程成用数组记录遇到的元素。

step 2：分别在搜索二叉树中找到p和q两个点，并记录各自的路径为数组。

step 3：同时遍历两个数组，比较元素值，最后一个相等的元素就是最近的公共祖先。

/*
 * 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

    if (!root) return null;

    // 先比较 p 和 q的大小
    const [max, min] = p > q ? [p, q] : [q, p];

    // min max root
    // min root max
    // min root/max
    if (root.val > min) {
        if (max >= root.val) {
            // min root max : 那返回 root
            // min root/max : 那返回 root
            return root.val;
        } else {
            // min max root : 继续向下寻找
            return lowestCommonAncestor(root.left, p, q);
        }
    }

    // root min max
    // root/min max
    else {
        // root/min max
        if (root.val === min) {
            return root.val;
        } else {
            // root min max: 向右下寻找
            return lowestCommonAncestor(root.right, p, q);
        }
    }
}
module.exports = {
    lowestCommonAncestor: lowestCommonAncestor,
};