From dumbest to the coolest in C, four different solutions


  • 0

    The first solution is quoted from the version-I of the problem.


    //AC - 24ms;
    struct TreeNode* lowestCommonAncestor( struct TreeNode* root, struct TreeNode *p, struct TreeNode* q )
    {
        if(!p) return q;
        if(!q) return p;
        if(!root || root == p || root == q) return root;
        struct TreeNode *left = lowestCommonAncestor(root->left, p, q);
        struct TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if(left&&right) return root;
        if(!left) return right;
        if(!right) return left;
    }
    

    Actually we can take advantage of the Binary Search Tree considering its value part to make the process more clear and simple.

    //AC - 20ms;
    struct TreeNode* lowestCommonAncestor( struct TreeNode* root, struct TreeNode *p, struct TreeNode* q )
    {
        if(root == NULL || root == p || root == q ||
                (root->val > p->val && root->val < q->val) ||
                (root->val < p->val && root->val > q->val)) return root; //all the possible cases;
        if(root->val > p->val && root->val > q->val) //in the left sub;
            return lowestCommonAncestor(root->left, p, q);
        else //in the right sub;
            return lowestCommonAncestor(root->right, p, q);
    }
    

    As we have checked the previous solution, the complexity and redundancy is quite annoying. So let's try to reverse the sequence of the checking and then we get the following terse solution!

    struct TreeNode* lowestCommonAncestor( struct TreeNode* root, struct TreeNode *p, struct TreeNode* q )
    {
        if(p->val<root->val && q->val<root->val) return lowestCommonAncestor(root->left, p, q);
        else if(p->val>root->val && q->val>root->val) return lowestCommonAncestor(root->right, p, q);
        return root;
    }
    

    Of course we can simply convert it to iterative version as follows:

    struct TreeNode* lowestCommonAncestor3( struct TreeNode* root, struct TreeNode *p, struct TreeNode* q )
    {
        while(1)
        {
            if(p->val<root->val && q->val<root->val) root = root->left;
            else if(p->val>root->val && q->val>root->val) root = root->right;
            else return root;
        }
    }

Log in to reply
 

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