使用递归检查树路径中是否存在和

Question

我试图解决树中的一个问题，我们必须检查完整路径（从根到叶）是否会导致求和值（由用户给出）。我成功地做到了这一点，下面是代码

    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null)
        {
            return false;
        }
        sum = sum - root.val;
        if(sum==0 && root!=null && root.left==null && root.right==null)
        {
            return true;
        }
        boolean b1 = hasPathSum(root.left,sum);
        boolean b2 = hasPathSum(root.right,sum);
        return b1||b2;
    }
}

我理解代码的主要问题是，当我们向下移动root.left的递归函数时，总和会发生变化，当总和在<--plhd中传递时，总和的值会发生变化--1/>语句。我们希望在第二个函数中传递的总和值是那个给定点的值（由于总和通过第一个函数传递，应该会改变），但是这段代码似乎仍然正常工作。

Answer 1

您的“sum”（方法签名的形式参数）被声明为基元类型。这将确保其值仅存在于当前堆栈帧中。如果沿着递归链进行更改，则该更改将局限于发生递归调用的帧。

每个方法调用“看到”它自己的sum变量的副本和值，直到该方法返回一个值，并将更新后的值传递给递归链。

Answer 2

递归的美妙之处在于，当堆栈展开时，它将具有与当前方法相同的值。

一堆就像一堆。因此，顶部的方法就是当前正在执行的方法。每当执行一个新方法时，先前的方法及其状态都会被冻结。因此，在下面的堆栈描述中，当调用Latest Call时，它下面的方法没有变化。

hasPathSum(root.left.left, sum - root.val - root.left.val); --> Latest Call
hasPathSum(root.left, sum - root.val); --> Mid Call
hasPathsum(root, sum); --> First Call

Answer 3

sumint的类型被声明为原语。在Java中，当使用args调用方法时，该方法将获得args值的副本。基元类型将获得值的副本，但类实例（对象）方法将获得对象引用的副本。