二叉树路径和问题中的递归逻辑输出错误

Question

我正在尝试使用Leetcode中的递归来解决路径和问题。我不擅长用递归解决问题。我看到了一些其他的解决方案，但我试图自己实现一个。我不明白我在我的方法中做错了什么。如果有人帮助我理解我做错了什么，我将非常感谢你的帮助。提前谢谢。

问题陈述：给定二叉树的根和整数targetSum，如果树有根到叶的路径，则返回true，这样沿路径的所有值相加等于targetSum。

叶是没有子节点的节点。

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(checkSum(root, targetSum) == 1) return true;
        return false;
    }
    
    public int checkSum(TreeNode root, int targetSum){
        if(root == null) return 0;
        if(root.left != null){
           // Assuming my checkSum() function already works, I want to get the left tree sum
            int left = checkSum(root.left, targetSum-root.val);
            // Adding the root value to the left tree sum to check if it equals to targetSum
            // If it matches, it returns 1
            if(left+root.val == targetSum){
                return 1;
            };
        }
        if(root.right != null){
           // Assuming my checkSum() function already works, I want to get the right tree sum
            int right = checkSum(root.right, targetSum-root.val);
            // Adding the root value to the right tree sum to check if it equals to targetSum
            // If it matches, it returns 1
            if(right+root.val == targetSum){
                return 1;
            };
        }
        // When everything above, does not match, it returns 0
        return 0;
    }
}

我的方法：我在研究递归时读到的是，你必须相信你的函数是有效的。因此，相信我假设调用校验和（root.left，targetSum-root.val）应该返回左子树的和。之后，我添加根。val向左求和，并检查它是否等于targetSum。我对正确的子树也做了同样的事情。我的函数当前输出错误。有人能帮我理解我在哪里用例子做错了吗。提前感谢你的帮助。

Answer 1

代码的关键问题是，您实际上没有涵盖基本场景。根据您的代码，当我们到达一个叶子时，我们只返回0。您根本不考虑targetSum变量。想想看。想象一个非常简单的例子，在这个例子中，你有一个根，有两个子元素，它们的值分别为10、5、20和targetSum=30。此输入的答案应为true，但函数将返回false，因为它只是忽略堆栈底部的targetSum（换句话说，基本情况）。

因此，对基本情况的检查可能如下所示：

if (root.left == null && root.right == null) {
    //some logic 
}

从基本检查，如果语句

if(left+root.val == targetSum){
   return 1;
};
if(right+root.val == targetSum){
   return 1;
};

不正确，因为您的左/右是检查和的结果，它只返回1或0。将其添加到root.val中是没有意义的，因为它并不意味着某个叶子的总和。我会把第一个if语句替换为

if (left == 1) {
    return 1;
} 

第二个if语句也应该这样做。我希望这会对你有所帮助。