Least Common Ancestor

• Time : $O(v + d)$
• Space : $O(v)$

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 void dfs(TreeNode* node, int par, int dep, unordered_map<int,int>& level, unordered_map<int,int>& parent) {
     parent[node->val] = par;
     level[node->val] = dep;
     if(node->left) dfs(node->left, node->val, dep + 1, level, parent);
     if(node->right) dfs(node->right, node->val, dep + 1, level, parent); 
 }
int Solution::lca(TreeNode* A, int B, int C) {
    unordered_map<int, int> level, parent;
    dfs(A, -1, 0, level, parent);
    if(!level.count(B) or !level.count(C)) return -1;
    while(level[B] != level[C]) {
        if(level[B] > level[C]) B = parent[B];
        else C = parent[C];
    }
    while(B != C) {
        B = parent[B];
        C = parent[C];
    }
    return B;
}