递归方法中使用ref参数为何会引发问题？

问题背景 #

给定二叉树的根节点root和整数targetSum，需判断是否存在从根到叶子的路径，其节点值之和等于targetSum。

传值版本的正确代码 #

以下是可正确解决问题的传值版本代码（targetSum=22时已通过LeetCode验证）：

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
 }

namespace BinaryTree
{
    internal class Program
    {
        static void Main(string[] args)
        {
            TreeNode root = new TreeNode(5);
            TreeNode a = new TreeNode(4);
            TreeNode b = new TreeNode(11);
            TreeNode c = new TreeNode(7);
            TreeNode d = new TreeNode(2);
            TreeNode e = new TreeNode(8);
            TreeNode f = new TreeNode(13);
            TreeNode g = new TreeNode(4);
            TreeNode h = new TreeNode(1);
            root.left = a;
            root.left.left= b;
            root.left.left.left = c;
            root.left.left.right= d;
            root.right = e;
            root.right.left= f;
            root.right.right= g;
            root.right.right.right= h;
            int targetSum = 22;
            bool hasPathSum = HasPathSum(root, targetSum);
        }

        static bool HasPathSum(TreeNode root, int targetSum)
        {
            if (root == null)
                return false;
            int currentSum = 0;
            return PathSum(root, targetSum, currentSum);
        }

        static bool PathSum(TreeNode root, int targetSum, int currentSum)
        {
            if (root == null)
                return false;
            currentSum += root.val;
            bool lPath = PathSum(root.left, targetSum, currentSum);
            bool rPath = PathSum(root.right, targetSum, currentSum);
            if (root.left == null && root.right == null && currentSum == targetSum)
                return true;
            else if (lPath == true || rPath == true)
                return true;
            return false;
        }
     }
  }

传值版本正确的原因 #

传值传递时，currentSum是栈上的局部变量，每次递归调用都会创建该变量的独立副本。当递归栈帧弹出（返回上层调用）时，上层的currentSum会恢复到之前的状态，不会被下层的修改影响，因此能准确计算每条从根到叶子路径的节点值之和。

ref传递版本的问题代码 #

将currentSum改为ref参数传入后，代码出现逻辑错误：

static bool HasPathSum(TreeNode root, int targetSum)
{
    if (root == null)
        return false;
    int currentSum = 0;
    return PathSum(root, targetSum, ref currentSum);
}

static bool PathSum(TreeNode root, int targetSum, ref int currentSum)
{
    if (root == null)
        return false;
    currentSum += root.val;
    bool lPath = PathSum(root.left, targetSum, ref currentSum);
    bool rPath = PathSum(root.right, targetSum, ref currentSum);
    if (root.left == null && root.right == null && currentSum == targetSum)
        return true;
    else if (lPath == true || rPath == true)
        return true;
    return false;
}

此时currentSum会累加所有访问过的节点值，最终变为所有节点值的总和55，无法正确判断单条路径的和是否等于targetSum。

疑问解答 #

你的假设完全正确：ref传递本质上是传递变量的内存地址（类似C/C++中的&currentSum），所有递归调用操作的都是同一个currentSum变量。

具体差异解释：

1. 传值传递：每次递归调用时，currentSum的当前值会被复制到新的栈帧中，下层递归对currentSum的修改仅作用于副本，不会影响上层的变量值。因此每条路径的和计算是独立的，能正确回溯到路径分支前的状态。
2. ref传递：所有递归调用共享同一个currentSum的内存空间，修改操作直接作用于原变量。遍历左子树时累加的数值不会在返回时自动回退，遍历右子树时会继续在左子树的总和上累加，最终所有节点值都被计入总和，导致路径和计算错误。

如果要让ref版本正确工作，需要手动实现回溯逻辑：在调用完左右子树后，将当前节点的值从currentSum中减去，恢复到进入当前节点前的状态，代码修改如下：

static bool PathSum(TreeNode root, int targetSum, ref int currentSum)
{
    if (root == null)
        return false;
    currentSum += root.val;
    try
    {
        bool lPath = PathSum(root.left, targetSum, ref currentSum);
        bool rPath = PathSum(root.right, targetSum, ref currentSum);
        if (root.left == null && root.right == null && currentSum == targetSum)
            return true;
        return lPath || rPath;
    }
    finally
    {
        // 回溯：减去当前节点值，恢复状态
        currentSum -= root.val;
    }
}

内容的提问来源于stack exchange，提问作者Vikram Singh