c - 需要递减递归树函数中的计数器，但仅当我在树中移动 "upwards"时

Question

我正在编写一个递归函数来查找是否存在从根到叶子的路径总和达到某个数字(用户输入总和)。每次我进入新的递归调用时，我都会使用 node->data 的值来增加 current_sum 的值。 Current_sum 在函数外部声明/初始化。因此，这可以很好地将总和传递到最左边的叶子。然而之后， current_sum 只是不断增加，因为我没有适当的减量操作来配合它。因此，如果在右分支中确实存在一条加起来达到一定数字的路径，例如: 1 2 @ @ 3 @ @，并且我检查路径 sum = 4, (1+3)，则不会得到该值。 (如果我检查 sum=3 (1+2)，它确实得到了它。)

所以我正在代码中寻找正确的位置来放置减量操作。我在想:current_sum -= root->data。然而我尝试把它放在很多不同的地方，但似乎所有的地方都是错误的。要么它们破坏原来的跟踪器，甚至到达最左边的第一片叶子。或者它们根本不递减(如果我将其放在左/右递归调用之后)。我还确实需要它在上升时保持递减，但在下降时保持递增。有没有办法用代码编写这个，我很好奇？或者，这只是一个糟糕的算法/方法吗？

我已经看到了解决此问题的其他方法，例如 https://www.geeksforgeeks.org/root-to-leaf-path-sum-equal-to-a-given-number/ ，这看起来真的很好，我只是想知道是否有办法解决我开始的问题。

int current_sum = 0;

int sumPath(Node * root, int sum)
{
    if (root == NULL)
    {
        return 0;
    }

    current_sum += root->data;


    if ((root->left == NULL) && (root->right == NULL))
    {
        if (current_sum == sum)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }

    int the_left = sumPath(root->left, sum);
    int the_right = sumPath(root->right, sum);
    ////////////////////current_sum -= root->data; (?)

    if (the_left>0)
    {
        return the_left;
    }
    else if (the_right>0)
    {
        return the_right;
    }
    return 0;
}

Answer 1

由于没有将 current_sum 作为参数发送，您可能会得到无效的输出。因为 current_sum 需要针对特定​​的堆栈跟踪或函数调用进行更新，而不是针对所有函数调用进行更新。这可能会给你一个无效的状态。

更新

  int isPossible(Node * root, int currentSum, int sum) {
    if(!root) return 0;

    currentSum += root.node;

    // when you find the sum, and can't move further down
    if(sum == currentSum && root->left == null && root->right == null) return 1;

    int flag = 0;
    // going down on left side
    flag = isPossible(root->left, currentSum, sum);

    // needs to check right side, only when you couldn't find sum on left
    if(!flag)
        flag = isPossible(root->right, currentSum, sum);

    // return the state
    return flag;
 }