你的代码存在一些问题,主要是路径的递归计算没有正确处理。具体来说,当前节点的 curSum
应该在每次调用时保持一致,而不是在左右子树的递归调用中重置为0。
下面是修改后的代码,并附带详细解释:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var result int
// Backtrace 函数用于从每个节点出发进行 DFS 搜索
func Backtrace(root *TreeNode, targetSum, curSum int) {
if root == nil {
return // 如果当前节点为空,则返回
}
// 更新当前路径和
curSum += root.Val
// 检查当前路径和是否等于目标值,如果相等则结果加一
if curSum == targetSum {
result++
}
// 继续搜索左子树和右子树,传入当前路径和 curSum
Backtrace(root.Left, targetSum, curSum)
Backtrace(root.Right, targetSum, curSum)
// 注意:这里不需要将 curSum 重置为0,因为我们希望保持累计路径和
}
// pathSum 函数负责遍历每个节点作为起点进行 DFS 搜索
func pathSum(root *TreeNode, targetSum int) int {
result = 0
// 从每个节点开始进行 DFS 搜索
var dfs func(node *TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return // 如果当前节点为空,则返回
}
// 从当前节点出发进行路径查找
Backtrace(node, targetSum, 0)
// 继续向下遍历左子树和右子树作为新起点
dfs(node.Left)
dfs(node.Right)
}
dfs(root) // 开始从根节点进行搜索
return result
}
修改与解释:
Backtrace 函数:
- 在进入函数时检查
root
是否为空。 - 每次更新
curSum
为之前累积值加上当前节点的值。 - 检查
curSum
是否等于targetSum
,如果相等则增加结果计数。 - 遍历左右子树时,将更新后的
curSum
传递下去。
- 在进入函数时检查
pathSum 函数:
- 定义一个内部的
dfs
函数,从每个节点开始执行深度优先搜索(DFS)。 - 对于每一个以该节点为起点的路径,通过调用
Backtrace
来统计符合条件的路径数量。 - 然后递归地遍历左、右子树,以确保所有可能的起点都被考虑到。
- 定义一个内部的
通过这样的修改,你可以得到正确答案,也能确保所有从任何一个父节点到其任意子孙结点的有效路径都会被统计到。
内容由零声教学AI助手提供,问题来源于学员提问