Easy DFS approach in C++( easy to understand)


#1
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
bool is_there(TreeNode *root,vector<int>&v,int x)
{
    if(!root)
    {
        return false;
    }
    if(root->val==x)
    {
        v.push_back(root->val);
        return true;
    }
    if(is_there(root->left,v,x) || is_there(root->right,v,x))
    {
        v.push_back(root->val);
        return true;
    }
    else
    {
        return false;
    }
}
int Solution::lca(TreeNode* A, int B, int C) 
{
    vector<int>first,second;
    bool f=is_there(A,first,B);
    bool s=is_there(A,second,C);
    if(!f || !s)
    {
        return -1;
    }
    int i=first.size()-1,j=second.size()-1;
    while(i>0 && j>0 && first[i-1]==second[j-1])
    {
        i--;
        j--;
    }
    return first[i];
}