当前位置 博文首页 > 中流击水，浪遏飞舟：递归&&迭代&&剑指 Offer 6
大佬还是那个大佬，我还是那个菜鸡。
化繁为简，三种情况，（1）p，q都在左子树；（2）p，q都在右子树；（3）p，q异侧，直接返回根节点。
二叉搜索树性质：左孩子的值比当前节点值小，右孩子的值比当前节点值大。
参考大佬的力扣题解：
面试题68 - I. 二叉搜索树的最近公共祖先（迭代 / 递归，清晰图解）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root){
return NULL;
}
if(root->val > p->val && root->val > q->val){
return lowestCommonAncestor(root->left,p,q);
}
if(root->val < p->val && root->val < q->val){
return lowestCommonAncestor(root->right,p,q);
}
return root;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root){
if(root->val > p->val && root->val > q->val){
root=root->left;
}
else if(root->val < p->val && root->val < q->val ){
root=root->right;
}
else{
break;
}
}
return root;
}
};
