C++ - Übergabe durch Referenz in Rekursion

Question

bool roottoleafsumequaltox(BinaryTreenode<int>* root, int &x) 
{ 
    if(root == NULL) 
    { 
     return (x==0); 
    } 
    else 
    { 
    bool ans = false; 
    x = x - root->data; 

    if(x == 0 && root->left == NULL && root->right == NULL) 
    { 
     return true; 
    } 

    if(root->left) 
     ans = ans || roottoleafsumequaltox(root->left, x); 

    if(root->right) 
     ans = ans || roottoleafsumequaltox(root->right, x); 

    return ans; 
    } 
} 

Es muss zurückgegeben werden, ob die Summe von Wurzel zu Blat einer gegebenen Zahl x entspricht. Ich denke das Problem liegt darin, durch Verweis zu gehen und ich kann es nicht erkennen ... Es gibt immer falsch als Antwort, auch wenn es wahr ist!

Answer 1

Ich bin nicht sicher zu under was wollen Sie, aber ich vermute, dass das Problem ist, dass Sie x

x= x- root->data; 

ändern, so, wenn Sie x zu roottoleafsumequaltox()

ans= ans || roottoleafsumequaltox(root->left, x); 
ans = ans || roottoleafsumequaltox(root->right, x); 

passieren Sie einen Pass x mit einem modifizierten Wert

Ich nehme an, Sie könnten vermeiden, zu ändern x an d Legen Sie if auf diese Weise schreiben

if((x == root->data) && (root->left == nullptr) && (root->right == nullptr)) 

Answer 2

Ja, das ist das Problem mit Übergabe als Referenz. x Wert wird mit jedem Knoten-Traversal immer kleiner.

Erhalten Sie einfach Referenzübergang loswerden, und dann aktualisieren:

roottoleafsumequaltox(root->left/right, (x - root->data)) 

und Check-out für (leaf_node->data == x).

Vergewissern Sie sich, für die Optimierung, die Sie nicht direkt childtree auch gehen und überprüfen, ob Sie bereits festgestellt, dass eine der Route von der Wurzel (oder jedem anderen Knoten) zu Blatt Summe gibt == x (an dieser Position).