Using backtracking


#1

/**

  • Definition for binary tree
  • struct TreeNode {
  • int val;
    
  • TreeNode *left;
    
  • TreeNode *right;
    
  • TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    
  • };
    /
    void search(TreeNode
    A, int value, bool &flag)
    {
    if(A==NULL)
    {
    return ;
    }
    search(A->left,value,flag);
    if(A->val==value)
    {
    flag=true;
    return;
    }
    search(A->right,value,flag);
    }
    void path(TreeNode* A, vector<vector> &v, vector &s, int value)
    {
    if(A==NULL)
    {
    return;
    }
    s.push_back(A->val);
    if(A->val==value)
    {
    // for(int i=0;i<s.size();i++)
    // {
    // printf("%d “,s[i]);
    // }
    v.push_back(s);
    return;
    }
    path(A->left,v,s,value);
    path(A->right,v,s,value);
    s.pop_back();
    }
    int Solution::lca(TreeNode* A, int B, int C) {
    bool flag1=false;
    search(A,B,flag1);
    bool flag2=false;
    search(A,C,flag2);
    if(flag1==false || flag2==false)
    {
    return -1;
    }
    vector<vector> v;
    vector s;
    path(A,v,s,B);
    s.clear();
    path(A,v,s,C);
    // for(int i=0;i<v.size();i++)
    // {
    // for(int j=0;j<v[i].size();j++)
    // {
    // printf(”%d ",v[i][j]);
    // }
    // }
    int i,j;
    for(i=0,j=0;i<v[0].size(),j<v[1].size();i++,j++)
    {
    if(v[0][i]!=v[1][j])
    {
    break;
    }
    }
    return v[0][i-1];
    }