Solution faster than editorial


#1

In editorial tree is traversed 3 times.
First two traverses to find if given numbers exist in tree or not.
This time can be saved as done in following code

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
bool bexists = false, cexists = false; 
 
inline void store(int val, int B, int C) {
    if (val == B)
        bexists = true;
    if (val == C)
        cexists = true;
} 
 
inline bool exist(int val) {
    return val != -1;
}

int util(TreeNode* A, int B, int C) {
    if (!A) {
        return -1;
    }
    
    int left = util(A->left, B, C);
    int right = util(A->right, B, C);   
    
    store(A->val, B, C);
    store(left, B, C);
    store(right, B, C);
    
    if (exist(left) && exist(right)) {
        return A->val;
    }
    if (A->val == B || A->val == C) {
        return A->val;
    }
    if (exist(left)) {
        return left;
    }
    if (exist(right)) {
        return right;
    }
    return -1;
}
 
int Solution::lca(TreeNode* A, int B, int C) {
    bexists = cexists = false;
    int res = util(A, B, C);
    return (bexists && cexists) ? res : -1;
}