提问人:badavadapav 提问时间:11/13/2023 最后编辑:petezurichbadavadapav 更新时间:11/13/2023 访问量:48
路径总和 - 我哪里出错了?
Path Sum - Where am I going wrong?
问:
Leetcode 问题 #112 - 路径和
给定二叉树的根和整数 targetSum,如果树具有根到叶的路径,则返回 true,以便将路径上的所有值相加等于 targetSum。
叶子是没有子节点的节点。
这是我的英文方法 - 我使用 DFS 遍历树。当我到达第一个 else 语句中的叶节点时,我将路径值的总和附加到列表中。最后,我检查其中是否包含。如果是,则返回 否则返回 。my_list
targetSum
True
False
# 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 语句停止递归调用,但这也没有用。try
except
答:
1赞
Tenatus
11/13/2023
#1
该函数缺少 return 语句,因此它始终返回 ,其计算结果为 。最后一行应更改为 。hasPathSum
None
False
return build_some(root, 0)
(使用 def 定义的 Python 函数不会像 lambda 那样自动返回最后一个表达式的值。
下一个:深度优先搜索逻辑递归函数
评论
return build_some(root, 0)