-2

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

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)

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

4

2 回答 2

3

首先，您对以下两个return陈述是正确的：

        return dfs(remainingSum,root)
        
        return False

return不可能执行第二条语句。所以让我们看看程序的其余部分。首先，逻辑应该是什么？

  1. 首先，hasPathSum在入口检查以查看是否root评估为True，如果不是，则返回False。这很好。
  2. 然后它应该检查根节点的值是否等于传递的targetSum值，因为如果是，我们可以立即返回True。targetSum但是相反，您的程序会立即从yield中减去根节点的值，remainingSum而您从不检查targetSum. 所以想象一棵树，它只有一个没有叶子的根，它的值为5，我们调用hasPathSum并targetSum设置为 5。我们应该返回True。请记住：叶子是没有子节点的节点。因此，这棵树的根也是叶子，应该检查。
  3. 否则，递归调用hasPathSum当前节点的左树传递remainingSum. 如果返回值为True，则返回True。（无需先检查左树值是否存在，if root.left:因为当您hasPathSum递归调用时，它已经在检查if not root:）
  4. 否则返回您通过调用hasPathSum正确的树传递的值remainingSum。
  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)
于 2021-07-06T11:27:23.457 回答
0
  1. 你不应该在一个函数中返回两次。你应该返回dfs.
  2. 您的dfs函数退出条件错误，您需要remainingSum在运行到下一个 dfs 之前检查。
  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.
于 2021-07-06T10:33:47.370 回答