c - 确保具有多个返回值的递归函数 "Preserve"期望的结果

Question

考虑这段代码(引自 geeksforgeeks.org，作者 Tushar Roy)如果从根到叶的路径具有总和为指定值的键，则计算真或假:

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 运算符他返回是为了避免用返回的假覆盖返回的真。我已将代码重构为:

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 运算符可以有效防止递归返回的覆盖，有哪些最佳方法可以将值传递到递归调用中？

编辑

反过来，让我们考虑一个稍微做作的例子；给定一棵排序不正确的二叉树(例如，键 100 作为根，左 child 的键为 5，右 child 的键为 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->item) 调用.从根本上说；我们被迫从根部向下走两个分支以探索并找到可能在树中任何位置的键(甚至是根本身!)我们知道我们必须进行分配以“拉出”正确的键，但是这会除非我们对每个分配进行某种有界检查，否则很可能会覆盖上一次调用的“真实”最小值(当前编写方式)，例如

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

我们也许还可以有两个单独的变量(毕竟这是一棵二叉树)，它们指定左边的最小值和右边的最小值，并且只返回两者中的最小值。在这些情况下，我仍然使用某种临时变量来返回其原始调用者。最后，我对在设计递归算法时避免此类错误的通用启发式方法感到好奇。

Answer 1

这是未经优化的原始示例。您会发现该算法现在更清晰了。

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 中我们只需要找到三个值中的最小值 - 所以我们做到了。

我已经上传了 a complete working example具有用于测试和生成测试树的附加功能。