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

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)

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

Answer 1

你不应该 return 两次 function.You 应该 return dfs 的结果。
您的 dfs 函数退出条件错误，您需要检查运行之前的 remainingSum 进入下一个 dfs。
当你找到一片叶子时，你需要检查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.

Answer 2

首先，关于两个 return 陈述，你是对的：

        return dfs(remainingSum,root)
        
        return False

无法执行第二个 return 语句。那么让我们看看程序的其余部分。首先，逻辑应该是什么？

首先，hasPathSum 在输入时检查 root 是否为 True，如果不是 return False。这个不错。
然后它应该检查根节点的值是否等于传递的 targetSum 值，因为如果是，我们可以立即 return True。但是您的程序会立即从 targetSum 中减去根节点的值，得到 remainingSum 而您从不检查 targetSum。想象一下，一棵树只包含一个没有叶子的根，其值为 5，我们调用 hasPathSum 并将 targetSum 设置为 5。我们应该 returning True。记住：一个叶子是一个没有children.的节点，因此这棵树的根也是叶子，应该检查。
否则，在当前节点的左树上递归调用hasPathSum传递remainingSum。如果 return 值为 True，则 return True。（不需要先检查左树值是否存在 if root.left: 因为当你递归调用 hasPathSum 时它已经在检查 if not root:）
否则 return 您通过在右树上调用 hasPathSum 获得的值传递 remainingSum。
不需要单独的 dfs 函数。

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

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)

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

Why isn't the return function inside my recursive call being executed?

python

binary-tree