16 ms C code - easy to understand


  • 0
    V
    bool check(struct TreeNode * source, struct TreeNode* dest)
    {
        if(source==NULL)
        return false;
        else if(source==dest)
        return true;
        else
        return check(source->left,dest)||check(source->right,dest);
    }
    void findht(struct TreeNode* root,struct TreeNode* fnd,struct TreeNode ** ancs, int level, int * ht)
    {
        if(root==NULL)
        return;
        if(root->left==fnd||root->right==fnd)
        (*ancs)=root;
        else if(root==fnd)
        (*ht)=level;
        findht(root->left,fnd,ancs,level+1,ht);
        findht(root->right,fnd,ancs,level+1,ht);
    }
    struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) 
    {
        if(p==NULL||q==NULL||root==NULL)
        return NULL; 
        else if(p==root||q==root)
        return root;
        else if(p==q)
        return p;
        else
        {
            int htp=0,htq=0,levelp=0,levelq=0;
            struct TreeNode * ancsp=root,*ancsq=root;
            bool checkp=false,checkq=false;
            findht(root,p,&ancsp,levelp,&htp);
            findht(root,q,&ancsq,levelq,&htq);
            if(htp>htq)
            checkp=check(q,p);
            else if(htq>htp)
            checkq=check(p,q);
            if((htp==htq)||(checkp==false&&checkq==false))
            lowestCommonAncestor(root,ancsp,ancsq);
            else if(checkp==true)
            return q;
            else if(checkq==true)
            return p;
        }
    }

Log in to reply
 

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