Very easy C++ solution with LCA


#1
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

void dfs(TreeNode *A,int p,int L,unordered_map<int,int>&par,unordered_map<int,int>&Level)
{
    if(A==NULL)return;
    Level[A->val]=L;
    par[A->val]=p;
    dfs(A->left,A->val,L+1,par,Level);
    dfs(A->right,A->val,L+1,par,Level);
}
int Solution::lca(TreeNode* A, int B, int C) {
    unordered_map<int,int>par,Level;
    if(A==NULL)return -1;
    dfs(A,A->val,0,par,Level);
    if(B!=A->val and Level[B]==0)return -1;

    if(C!=A->val and Level[C]==0)return -1;

    if(Level[B]>Level[C])swap(B,C);

    while(Level[C]!=Level[B]){
        C=par[C];
    }
    if(B==C)return B;
    while(par[B]!=par[C]){
        B=par[B];
        C=par[C];
    }
    return par[B];
    
}