题解 | JZ68 二叉搜索树的最近公共祖先
这题和上一题JZ86不一样。
虽然JZ86的方法是通用的方法，但是我们要针对这道题给出的多的条件进行优化，从而达到最优的算法（不然这二叉搜索树的条件不是白给了）。
对于二叉搜索树而言，它一定是节点的左子树都小于该节点，右节点都大于该节点。
所以，我们要利用这个条件,满足这个条件的，最下层的节点，就是我们要搜索的节点。
但这有一个例外。
如果p节点的祖先是q呢？
如果我们不考虑这个情况，一味地取最下层满足条件的节点作为答案，我们则会取成p节点作为答案，而非正确答案q节点。
因此，我们要特殊判断这个情况。
if (root->val != minn && root->val != maxn) ans = root;
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param p int整型
* @param q int整型
* @return int整型
*/
TreeNode* ans = nullptr;
int lowestCommonAncestor(TreeNode* root, int p, int q) {
// write code here
int minn = min(p, q);
int maxn = max(p, q);
findP(root, minn, maxn);
return ans->val;
}
void findP(TreeNode* root, int minn, int maxn) {
if (!root) return;
if (root->val >= minn && root->val <= maxn) {
if (!ans) ans = root;
else {
if (root->val != minn && root->val != maxn) ans = root;
}
}
if (root->val <= minn) {
findP(root->right, minn, maxn);
}
else if (root->val >= maxn) {
findP(root->left, minn, maxn);
}
return;
}
};
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @param p int整型
# @param q int整型
# @return int整型
#
class Solution:
ans = None
def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
# write code here
minn = min(p, q)
maxn = max(p, q)
self.findP(root, minn, maxn)
return self.ans.val
def findP(self, root, minn, maxn):
if not root:
return
if root.val >= minn and root.val <= maxn:
if not self.ans:
self.ans = root
else:
if root.val != minn and root.val != maxn:
self.ans = root
if root.val <= minn:
self.findP(root.right, minn, maxn)
elif root.val >= maxn:
self.findP(root.left, minn, maxn)
return
查看5道真题和解析