路径总和 - 我哪里出错了?

Path Sum - Where am I going wrong?

提问人:badavadapav 提问时间:11/13/2023 最后编辑:petezurichbadavadapav 更新时间:11/13/2023 访问量:48

问:

Leetcode 问题 #112 - 路径和

给定二叉树的根和整数 targetSum,如果树具有根到叶的路径,则返回 true,以便将路径上的所有值相加等于 targetSum。

叶子是没有子节点的节点。

这是我的英文方法 - 我使用 DFS 遍历树。当我到达第一个 else 语句中的叶节点时,我将路径值的总和附加到列表中。最后,我检查其中是否包含。如果是,则返回 否则返回 。my_listtargetSumTrueFalse

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        my_list = []
        def build_some(root, cur_sum):
            if not root or targetSum == 0:
                return False 

            elif root.left or root.right:
                cur_sum += root.val
                build_some(root.left, cur_sum)
                build_some(root.right, cur_sum)
            
            else:
                my_list.append(cur_sum+root.val)

            if targetSum in my_list:
                return True
            else:
                return False
        build_some(root, 0)

我遇到以下测试用例的问题:

              5
           /     \
         4        8
        /        /  \
      11        13    4
    /    \             \
   7      2             1

此处,targetSum 为 22。路径 [5,4,11,2] 总和为 22,我的代码在识别这一点方面工作正常(我使用 验证了)。尽管如此,我的程序在应该返回 True 时返回 False。我哪里出了问题?print(my_list)

如果找到解决方案,我尝试使用 and in first else 语句停止递归调用,但这也没有用。tryexcept

python 数据结构 binary-tree

评论

2赞 Tenatus 11/13/2023
hasPathSum 缺少 return 语句。如果最后一行更改为 ?return build_some(root, 0)
0赞 badavadapav 11/13/2023
像魅力一样工作。不知道我是怎么错过的。谢谢。你可以添加你的回答作为答案,我会接受它。谢谢!

答:

1赞 Tenatus 11/13/2023 #1

该函数缺少 return 语句,因此它始终返回 ,其计算结果为 。最后一行应更改为 。hasPathSumNoneFalsereturn build_some(root, 0)

(使用 def 定义的 Python 函数不会像 lambda 那样自动返回最后一个表达式的值。