ツリー内で最も共通の祖先を見つける際にエラーが発生しました。

Question

ツリー内の2つの値のうち最も低い共通祖先を見つけようとしています。

私のアプローチは、ツリーの左下を横切って、個々のノードがそれらの下に両方のノードを持つ天気をチェックすることです。一致を与える最初のノードは、最低共通祖先です。

誰でも私にこの機能のエラーを教えてもらえますか？

/* 
Node is defined as 

typedef struct node 
{ 
    int data; 
    node * left; 
    node * right; 
}node; 

*/ 


bool find(node *root,int val) //to check if the value exist under the given node or not 
{ 
    if(root==NULL) 
     return false; 
    if(root->data==val) 
     return true; 

    if((root->left&&find(root->left,val))||(root->right&&find(root->right,val))) 
     return true; 
    return false; 
} 


node * lca(node * root, int v1,int v2) //to find the lowest common ancestor 
{ 
    if(root==NULL) 
     return NULL; 
    static node* ans=NULL; 
    lca(root->left,v1,v2); //traversing to the bottom of the tree 
    lca(root->right,v1,v2); 

    if((find(root->left,v1)&&find(root->right,v2))||(find(root->left,v2)&&find(root->right,v1))) //checking the existence of both nodes under the tree 
    { 
     if(ans==NULL) 
      ans=root; 
    } 

    return ans; //returning the lca 
} 

Answer 1

結果が見つかった場合、再帰関数はノードのみを返します。結果ノードが見つからない場合は、NULLを返します。ノードが見つかった場合は中断し、それ以外の場合は続行します。私は次のようにします：

node * lca(node * root, int v1,int v2) //to find the lowest common ancestor 
{ 
    if(root==NULL) 
     return NULL; 

    node* ans=NULL; 

    // search the left child tree 
    ans = lca(root->left,v1,v2); 
    if (ans != NULL) 
     return ans; // if you found it you are finished 

    // search the right child tree 
    ans = lca(root->right,v1,v2); 
    if (ans != NULL) 
     return ans; // if you found it you are finished 

    // test this tree node 
    if((find(root->left,v1)&&find(root->right,v2)) || 
     (find(root->left,v2)&&find(root->right,v1))) 
    { 
     // If the condition is true, this node is the result 
     return root; 
    } 

    return NULL; // Neither this node nor any subordinate node of this node is the result 
}