递归 - 与这个 BST 有什么区别？

Question

所以我有时会在递归上遇到一些问题。这两者在逻辑上的最终区别是什么：

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 *found = lca(root, 1, 2);
int answer = found->data;  // whatever you want

但第二个不可能是这样。

代码详细信息：https://ideone.com/oZdW6k

如果你不喜欢使用退货，可以将其固定为：

///////////////////////////////////////////////////////
// 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("%dn", 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
}