24ms C solution using recursion


  • 0
    Y
    bool exist(struct TreeNode* ances, struct TreeNode* desc){
        if(ances==NULL)
        return false;
        else if(ances==desc)
        return true;
        else return (exist(ances->left,desc)||exist(ances->right,desc));
    }
    struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
        if(root==p||root==q){
            return root;
        }
        bool pinleft=exist(root->left,p);
        bool qinleft=exist(root->left,q);
        if(qinleft!=pinleft){
            return root;
        }
        else if(qinleft&&pinleft){
            return lowestCommonAncestor(root->left,p,q);
        }
        else{
            return lowestCommonAncestor(root->right,p,q);
        }
        
    }

  • 0
    Y

    Oh I didn't consider that p or q may not be in the tree. I assumed p(or q) either in left or right


  • 0
    C

    @yuboh I think you don't have to. The problem is that "find the lowest common ancestor (LCA) of two given nodes in the BST."


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.