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);而不是隻是調用它。你只在根目錄時返回一個值，這就是爲什麼當你在main中得到正確的輸出時唯一的情況。

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"); 
}