【LeetCode 235.二叉搜索树的最近公共祖先】JavaScript/C++实现

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

说明：

1. 所有节点的值都是唯一的。
2. p、q 为不同节点且均存在于给定的二叉搜索树中。

例如，给定如下二叉搜索树:

root = [6,2,8,0,4,7,9,null,null,3,5]

示例：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。           

复制

思路分析

只要理清递归中过程即可。注意这是一棵二叉搜索树，满足

node.left.val < node.val < node.right.val

。

一共 4 种情况：

1. 如果 p 和 q 的节点在 root 的两侧，那么最近公共祖先节点就是 root
2. 如果 p.val 或者 q.val 等于 root.val，那么最近公共祖先节点就是 p 或 q
3. 如果情况 1 和 2 都不满足，说明 p 和 q 在 root 的同一侧：
   • 若 root.val 大于 p.val 和 q.val，那么往左侧递归
   • 若 root.val 小于 p.val 和 q.val，那么往右侧递归

解法 1: JavaScript 实现

// ac地址：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
// 原文地址：https://xxoo521.com/2020-04-18-lowest-common-ancestor-of-bst/
/**
 * @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) ||
        (root.val < p.val && root.val > q.val) ||
        root.val === p.val ||
        root.val === q.val
    ) {
        return root;
    } else if (root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else {
        return lowestCommonAncestor(root.right, p, q);
    }
};           

复制

解法 2: C++实现

由于这题的剑指 offer 的题库中没提供 js 语言环境，我用 c++实现了思路:

// ac地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
// 原文地址：https://xxoo521.com/2020-04-18-lowest-common-ancestor-of-bst
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (
            (root->val == p->val)
            || (root->val == q->val)
            || (root->val > q->val && root->val < p->val)
            || (root->val < q->val && root->val > p->val)
        ) {
            return root;
        } else if (root->val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else {
            return lowestCommonAncestor(root->right, p, q);
        }
    }
};           

复制