为什么递归调用中的返回函数没有被执行？

Question

感谢您的更正，我已经做了修改，但还有一个问题我无法解决：

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if not root:
            return False

        if not root.left and not root.right:
            if root.val ==targetSum:
                return True
            else:
                return False

        remainingSum = targetSum - root.val

        def dfs(remainingSum, root):
            dfs(remainingSum - root.left.val, root.left)
            dfs(remainingSum - root.right.val, root.right)

            if remainingSum == 0:
                return True

        return dfs(remainingSum, root)

在递归函数中，我返回什么？或者上面的代码现在正确了吗

Answer 1

首先，关于两个return语句，您是对的：

        return dfs(remainingSum,root)
        
        return False

第二个return语句不可能被执行。让我们看一下节目的其余部分。首先，逻辑应该是什么

1. 首先，条目上的hasPathSum检查root是否计算为True，如果不是，则返回False。这很好
2. 然后它应该检查根节点的值是否等于传递的targetSum值，因为如果等于，我们可以立即返回True。但是，您的程序会立即从targetSum中减去根节点的值，从而产生remainingSum，并且您永远不会检查targetSum。想象一下，一棵树只包含一个根，没有叶，其值为5，我们调用hasPathSum，将targetSum设置为5。我们应该返回True。请记住：Aleaf是一个没有子节点的节点<因此，这棵树的根也是一片叶子，应该检查一下
3. 否则，递归调用当前节点左树上经过remainingSum的hasPathSum。如果返回值为True，则返回True。（无需首先检查左树值是否与if root.left:一起存在，因为当您递归调用hasPathSum时，它已经在检查if not root:）
4. 否则，返回从通过remainingSum的右树上调用hasPathSum得到的值
5. 不需要单独的dfs函数

如果您只是使用TreeNode构造函数来创建和初始化树节点，那么您将“自下而上”创建节点，即在其父节点之前离开。例如：

node_1 = TreeNode(7)
node_2 = TreeNode(8)
node_3 = TreeNode(9, left=node_1, right=node_2)
node_4 = TreeNode(4, left=node_3)
node_5 = TreeNode(2, right=node_4)
node_6 = TreeNode(14)
root = TreeNode(6, left=node_5, right=node_6)

Answer 2

1. 函数中不应返回两次。应返回dfs的结果
2. 如果dfs函数的退出条件错误，则需要在运行到下一个dfs之前检查remainingSum
3. 当您找到一个叶子时，您需要检查remainingSum，而不是return None

代码：

    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        def dfs(remainingSum,root): 
            if not root.left and not root.right:
                if remainingSum == 0: 
                    return True
                else:
                    return False
            if root.left: 
                x = dfs(remainingSum-root.left.val, root.left)
            else:
                x = False
            if root.right: 
                y = dfs(remainingSum-root.right.val, root.right)
            else:
                y = False
            return x or y

        if not root: 
            return False
        return dfs(targetSum - root.val,root)

结果:

Runtime: 40 ms, faster than 83.76% of Python3 online submissions for Path Sum.
Memory Usage: 16 MB, less than 18.57% of Python3 online submissions for Path Sum.