确保具有多个返回的递归函数“保留”所需结果

Question

考虑这段代码（引用自geeksforgeeks.org，作者Tushar Roy），如果从根到叶的路径具有总和为指定值的键，它会计算true或false：

bool hasPathSum(struct node* node, int sum)
{
  /* return true if we run out of tree and sum==0 */
  if (node == NULL)
  {
     return (sum == 0);
  }

  else
  {
    bool ans = 0; 

    /* otherwise check both subtrees */
    int subSum = sum - node->data;

    /* If we reach a leaf node and sum becomes 0 then return true*/
    if ( subSum == 0 && node->left == NULL && node->right == NULL )
      return 1;

    if(node->left)
      ans = ans || hasPathSum(node->left, subSum);
    if(node->right)
      ans = ans || hasPathSum(node->right, subSum);

    return ans;
  }
}

在这段代码中，作者在对变量ans的赋值中使用了逻辑OR运算符，以避免用false覆盖true返回。我已将代码重构为：

int hasPathSum(Treelink tree, int sum){
    if ( !tree ) { //succesful path found
        return (sum == 0);
    } else {
        sum -= tree->item;
        if ( (sum == 0) && (!tree->left && !tree->right)) 
            return 1;
        return hasPathSum(tree->left, sum) || hasPathSum(tree->right, sum);
    } 
}

尽管在这种情况下使用临时变量和/或逻辑OR运算符显然可以有效地防止递归返回的覆盖，但在递归调用中携带值的最佳方法是什么？

编辑

相反，让我们考虑一个稍微人为的例子；给定一个顺序不正确的二叉树（例如，key 100作为根，左子键为5，右子键为2），从树中递归找到最小键。我会天真地这样处理：

免责声明：已编写但未编译。

int findMin(Tree tree, int min) {
    if (!tree) return 0; //defensive check

    if ( tree->item < min && (tree->left || tree->right) ) { 
        //Can go deeper and reestablish the min in both directions
        if ( tree->left ) 
            min = findMin(tree->left, tree->item);
        if ( tree->right ) 
            min = findMin(tree->right, tree->item);
    } else if ( tree->item >= min && (tree->left || tree->right ) ) {
        //can go deeper but should not reestablish the min
        if ( tree->left ) 
            min = findMin(tree->left, min);
        if ( tree->right ) 
            min = findMin(tree->right, min);
    } else {
        return min; //return min's final value
    }
}

它大概会通过findMin（testTree， testTree-

tmpmin = findMin(tree->left);
min = (min < tmpmin) ? min : tmpmin;  

我们也可能有两个单独的变量（毕竟这是一个二叉树），它们指定左min和右min，并且只返回这两个变量中的min。在这些情况下，我仍在使用某种临时变量来承载其原始调用方。最终，我对设计递归算法时避免这些类型错误的通用启发式很好奇。




Answer 1

编辑：我误解了原来的问题，所以福库的回答更贴切。

C（和大多数其他语言）中的逻辑or运算符执行所谓的短路：一旦找到一个正确的操作数，它就会停止计算操作数。所以如果hasPathSum（树-

这个问题有更详细的解释。它是为Java编写的，但C中的运算符的工作方式相同。

Answer 2

这里是没有优化的原始示例。您将看到算法现在更加清晰了。

bool hasPathSum(struct node* node, int sum)
{
  /* return true if we run out of tree and sum==0 */
  if (node == NULL)
     return (sum == 0);

  /* otherwise check both subtrees */
  int subSum = sum - node->data;
  return hasPathSum(node->left, subSum) ||  hasPathSum(node->right, subSum);
}

关于实际问题——如何在数据结构中对数据没有约束的这种递归中返回值。返回子树（或您实际查看的任何数据结构）的当前最小值工作得很好。

只需考虑问题，而不考虑实际的数据结构。

current = useful_start_value
for value in data:
    if binaryOp(current, value):
       current = value   

因此，对于每个值，都必须根据当前数据对其进行测试。对于findMin函数，这将生成以下代码。我已经适应了使用原始数据结构。

int findMin(struct node* node, int min) {
    if (!node) return min;
    if (node->data < min)
       min = node->data;

    int leftMin = findMin(node->left, min);
    if(leftMin < min)
       min = leftMin;

    int rightMin = findMin(node->right, min);
    if(rightMin < min)
       min = rightMin;

    return min;
}

这样写的话，您还可以清楚地看到访问节点的实际顺序。

我的一般建议是：

• 不要过早优化（而且很糟糕）
• 在源代码中的一个位置执行递归调用（如果可以的话）
• 尝试将问题视为局部问题-就像在findMin中，我们只需要找到三个值中的最小值-所以我们做到了

我上传了一个完整的工作示例，其中包含用于测试和生成测试树的附加功能。