题目描述:给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
说明:
例如,给定如下二叉搜索树: 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 种情况:
// 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);
}
};
由于这题的剑指 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);
}
}
};