Recursive solution in C, accepted as best and well-commented


  • 1
    //AC - 12ms - return the LCA or the node itself;
    struct TreeNode* lowestCommonAncestor( struct TreeNode* root, struct TreeNode *p, struct TreeNode* q )
    {
        if(!p) return q; //corner case to accelerate from 16ms to 12ms;
        if(!q) return p;
        //the essential part: 1. p or q is the ancestor; 
        //2. p or q are in different sub-trees so the LCA will be in the higher level;
        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; //in different sub-trees;
        if(!left) return right; //in the same sub-tree;
        if(!right) return left;
    }

  • 0

    Clean solution of C++ enclosed

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(!root || root==p || root==q) return root;
            TreeNode *l = lowestCommonAncestor(root->left, p, q), *r = lowestCommonAncestor(root->right, p, q);
            if(l && r) return root;
            return l? l:r;
        }
    };
    

Log in to reply
 

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