Short, Readable and Very Intuitive Solution | C++


#1

Idea:
We find the path to nodes with values B and C.
Using preorder traversal because we need the path from the root to the node.
Store them into 2 vectors and compare them side by side, the last element which is same is the answer.

void preorder(TreeNode* root, vector<int> current, vector<int>& answer, int key)
{
    if(root == NULL) return;
    current.push_back(root->val);
    if(root->val == key)
    {
        for(auto& c : current)
            answer.push_back(c);
        return;
    }
    preorder(root->left, current, answer, key);
    preorder(root->right, current, answer, key);
    
}
int Solution::lca(TreeNode* A, int B, int C) 
{
    vector<int> path_B, path_C, current;
    preorder(A, current, path_B, B);
    preorder(A, current, path_C, C);
    int answer = -1;
    for(int i = 0, j = 0; i<path_B.size() && j<path_C.size(); i++, j++)
    {
        if(path_B[i] == path_C[j])
            answer = path_B[i];
    }
    return answer;
}