在你的代码中,问题出现在 Backtrace
函数的调用逻辑上。你使用了深度优先搜索(DFS)来查找路径和,但在计算路径时,你同时处理了从根节点开始的新路径和从当前节点向下的路径,这导致了一些重复计数。
具体来说,以下几行代码存在问题:
Backtrace(root.Left, targetSum, 0)
Backtrace(root.Right, targetSum, 0)
这两行代码会尝试从每个子节点开始新的路径(curSum
被重置为 0
),而之后的调用又继续沿着原来的路径。这就导致了对相同路径的多次计数。
修复建议
你应该只在需要的时候重置 curSum
,并确保只有当到达一个叶子节点时才进行累计。这里是修改后的代码示例:
var result int
func Backtrace(root *TreeNode, targetSum int, curSum int) {
if root == nil {
return
}
// 更新当前路径和
curSum += root.Val
// 检查当前节点是否为叶子,并且当前路径和是否等于目标值
if curSum == targetSum {
result++
}
// 继续遍历左子树和右子树,传递当前累积的和
Backtrace(root.Left, targetSum, curSum)
Backtrace(root.Right, targetSum, curSum)
}
func pathSum(root *TreeNode, targetSum int) int {
result = 0
// 从根节点开始进行回溯
Backtrace(root, targetSum, 0)
return result
}
这个修改后的版本只会在遍历过程中更新 curSum
的值,而不会重新初始化它。因此,对于从某个节点开始的所有合法路径都会被正确地计算。
另外,如果你的需求是要找到所有可能的“从任意节点到任意其他节点”的有效路径,你需要在 pathsum
函数中增加对每个节点作为起点的调用。这样做可以确保每条有效路径都能被找到。例如:
func pathSum(root *TreeNode, targetSum int) int {
if root == nil {
return 0
}
// 从当前根结点作为起点进行 DFS 查找有效路径
count := findPathsFromNode(root, targetSum)
// 对左右子树递归统计,同时也从左右子树各自作为起点查找有效路径
count += pathSum(root.Left, targetSum)
count += pathSum(root.Right, targetSum)
return count
}
// 从给定结点出发寻找符合条件的有效路径数量
func findPathsFromNode(node *TreeNode, remaining int) int {
if node == nil {
return 0
}
// 当前剩余值减去该结点值,形成新的剩余值
remaining -= node.Val
count := 0
if remaining == 0 {
count++ // 找到了一个符合条件的有效途径
}
count += findPathsFromNode(node.Left, remaining)
count += findPathsFromNode(node.Right, remaining)
return count
}
这样的改动后,会更完整地满足题目的要求。希望这能够帮助你解决问题!
内容由零声教学AI助手提供,问题来源于学员提问