题解 | #二叉搜索树的最近公共祖先#
二叉搜索树的最近公共祖先
http://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f
这个题分类处理就好，我选择的是先序遍历，这样比较好处理。
情况1：发现节点值在寻找的两个节点值中间，并且不等于其中任何一个，不用找了，已经找到了。
情况2：发现节点值等于寻找的两个值中较小的那个，那么只要大的那个在当前节点的左子树上就找到了，否则继续。
情况3：发现节点值等于寻找的两个值中较大的那个，那么只要小的那个在当前节点的右子树上就找到了，否则继续。
情况4：发现节点值比两个最大值的还大，那么在左子树上查找就好。
情况5：发现节点值比两个最大值的还小，那么在右子树上查找就好。
都不满足，就返回-1。（前面5种情况已经包括所有情况了，这里兜底）
/**
* 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整型
*/
int lowestCommonAncestor(TreeNode* root, int p, int q) {
// write code here
if(root == NULL){
return -1;
}
if(root->val > min(p,q) && root->val < max(p,q)){
return root->val;
}
if(root->val == min(p,q) && findChild(root->right, max(p,q))){
return root->val;
}
if(root->val == max(p,q) && findChild(root->left, min(p,q))){
return root->val;
}
if(root->val > max(p,q)){
return lowestCommonAncestor(root->left, p, q);
}
if(root->val < min(p,q)){
return lowestCommonAncestor(root->right, p, q);
}
return -1;
}
bool findChild(TreeNode* root,int childVal){
if(root == NULL){
return false;
}
if(childVal < root->val){
return findChild(root->left,childVal);
}
if(childVal > root->val){
return findChild(root->right,childVal);
}
return true;
}
};
/**
* 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整型
*/
int lowestCommonAncestor(TreeNode* root, int p, int q) {
// write code here
if(root == NULL){
return -1;
}
// if(root->val > min(p,q) && root->val < max(p,q)){
// return root->val;
// }
// if(root->val == min(p,q) && findChild(root->right, max(p,q))){
// return root->val;
// }
// if(root->val == max(p,q) && findChild(root->left, min(p,q))){
// return root->val;
// }
if(root->val > max(p,q)){
return lowestCommonAncestor(root->left, p, q);
}
if(root->val < min(p,q)){
return lowestCommonAncestor(root->right, p, q);
}
return root->val;
}
// bool findChild(TreeNode* root,int childVal){
// if(root == NULL){
// return false;
// }
// if(childVal < root->val){
// return findChild(root->left,childVal);
// }
// if(childVal > root->val){
// return findChild(root->right,childVal);
// }
// return true;
// }
};
