c++ - 递归-此BST有什么区别？

Question

所以有时我会在递归上打h。逻辑上的最终最终区别是:

Node *lca(Node *root, int v1,int v2) {
    // Write your code here.
    if (root == NULL)
    {
        return NULL;
    }

    // If both v1 and v2 are less than node->data, lies on the left
    if (v1 < root->data && v2 < root->data)
    {
        return lca(root->left, v1, v2);
    }
    
    if (v1 > root->data && v2 > root->data)
    {
        // if v1 and v2 are greater than node->data, then it lies on
        // the right of the binary search tree
        return lca(root->right, v1, v2);
    }
    
    // Otherwise, we have one on the left and one on the right,
    // so let's return root as that will be our lowest common ancestor
    return root;
}

还有这个:

Node *lca(Node *root, int v1,int v2) {
    // Write your code here.
    if (root == NULL)
    {
        return NULL;
    }

    // If both v1 and v2 are less than node->data, lies on the left
    if (v1 < root->data && v2 < root->data)
    {
        lca(root->left, v1, v2);
    }
    
    if (v1 > root->data && v2 > root->data)
    {
        // if v1 and v2 are greater than node->data, then it lies on
        // the right of the binary search tree
        lca(root->right, v1, v2);
    }
    
    // Otherwise, we have one on the left and one on the right,
    // so let's return root as that will be our lowest common ancestor
    return root;
}

我有时试图在脑海中经历它，但后来我自己陷入了递归循环中!为什么后者不正确？

Answer 1

第二个不返回找到的内容。它仅返回NULL或root。
让我们尝试使用以下示例进行检查:

   3  <-- root
 /   \
1     5
 \   /
  2 4

如果调用lca(root, 1, 2)，则第一个返回Node实例的指针。
然后，您可以将其用作:

Node *found = lca(root, 1, 2);
int answer = found->data;  // whatever you want

但是第二个不能是这个。
有关代码的详细信息:https://ideone.com/oZdW6k
如果您不喜欢使用 yield ，则可以将其固定为:

///////////////////////////////////////////////////////
// The third one (no return, but fixed)
//////////////////////////////////////////////////////
void lca(Node *src, Node *dst, int v1, int v2) {
    if (src == NULL) {
        return;
    }

    if (v1 < src->data && v2 < src->data) {
        lca(src->left, dst, v1, v2);
        *dst = *src->left;
        return;
    }
    
    if (v1 > src->data && v2 > src->data) {
        lca(src->right, dst, v1, v2);
        *dst = *src->right;
        return;
    }

    *dst = *src;
}

int main(){
    // root = ..... (initialize whatever)
    Node result;
    lca(root, &result, 1, 2);
    printf("%d\n", result.data);
    return 0;
}

您可以在https://ideone.com/bLvAnw上进行检查
而且，我还能说一件事。
条件如下:

    if (v1 < src->data && v2 < src->data) {
        // left...
    } else if (v1 > src->data && v2 > src->data) {
        // right...
    } else {
        // current node
    }