【leetcode】剑指-68.1 二叉搜索树的最近公共祖先

sharlynOUO / 2023-08-19 / 原文

思路

首先保证传入的p.val<q.val. 最近公共祖先，只有三种可能，是root，在左子树，在右子树。
Cases:

root.val = p.val or q.val: return root
left.val= p.val , right.val = q.val: return root
q.val < root.val: goto left tree
p.val>root.val: goto right tree

代码

第一版，递归法

class Solution {
public:
    TreeNode* get_ancestor(TreeNode* root, TreeNode* p, TreeNode* q){ 
            if(root->val == p->val || root->val == q->val)
                return root;
            if(p->val < root->val && q->val > root->val)
                    return root;
            if(p->val > root->val)
                return get_ancestor(root->right,p,q);
            if(q->val < root->val)
                return get_ancestor(root->left,p,q);
            return NULL;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if(p->val < q->val)
           return get_ancestor(root,p,q);
        else
           return  get_ancestor(root,q,p);

    }
};

第二版，迭代法

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* ptr=NULL;
        if(p->val > q->val){
            ptr=p;
            p=q;
            q=ptr;
        }
        ptr=root;
        while(ptr){
            if(ptr->val == p->val || ptr->val == q->val)
                break;
            if(p->val<ptr->val && q->val>ptr->val)
                    break;
            if(q->val < ptr->val)
                ptr = ptr->left;
            else if(p->val > ptr->val)
                ptr = ptr->right;
        }
        return ptr;
    }
}

知识点：通俗易懂讲解二叉搜索树