Самый низкий общий предок BST (странное поведение в возвращаемом значении)

Question

Вот функция для поиска наименьшего общего предка дерева двоичного поиска. Она работает нормально, потому что в функции правильно печатается LCA, но в основной функции она работает, только если LCA равна корню, в противном случае возвращаетсяNULL. Может кто-нибудь объяснить, как?

node* FindLCA(node* root,int val1,int val2)
  {
 if(root->val<val1&&root->val>val2||root->val>val1&&root->val<val2||root->val==val1||root->v    al==val2)
    { cout<<"\n\n"<<"LCA of "<<val1<<"and "<<val2<<"is "<<root->val<<"\n";  //working correctly here
    return root;
    }

 if(root->val>val1&&root->val>val2)
    FindLCA(root->left,val1,val2);
 else
    FindLCA(root->right,val1,val2);
 }

 int main()
 {
  int arr[]={5,2,6,1,7,4,8,9};
  node* tree=buildtree(arr,8);
  printPretty((BinaryTree*)tree, 1, 0, cout);
  int a=1,b=2;
  node* lca=FindLCA(tree,a,b);
if(lca!=NULL) cout<<"\n\n"<<"LCA of "<<a<<"and "<<b<<"is "<<lca->val<<"\n";            //working only if LCA equals root's value
 system("pause");
  }   

Answer 1

Вы должны return FindLCA(root->right,val1,val2); вместо того, чтобы просто позвонить.Вы возвращаете значение только в корне, и именно поэтому это единственный случай, когда вы получаете правильный вывод в основном.

node* FindLCA(node* root,int val1,int val2)
{
  if((root->val<val1&&root->val>val2) || (root->val>val1&&root->val<val2) ||
      root->val==val1 || root->val==val2)
  { 
    cout<<"\n\n"<<"LCA of "<<val1<<"and "<<val2<<"is "<<root->val<<"\n";  //working correctly here
    return root;
  }

  if(root->val>val1&&root->val>val2)
    return FindLCA(root->left,val1,val2);   // RETURN VALUE HERE
  else
    return FindLCA(root->right,val1,val2);  // RETURN VALUE HERE
}

int main()
{
  int arr[]={5,2,6,1,7,4,8,9};
  node* tree=buildtree(arr,8);
  printPretty((BinaryTree*)tree, 1, 0, cout);
  int a=1,b=2;
  node* lca=FindLCA(tree,a,b);
  if(lca!=NULL) cout<<"\n\n"<<"LCA of "<<a<<"and "<<b<<"is "<<lca->val<<"\n";  //working only if LCA equals root's value
  system("pause");
}