ZBLOG

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ var result int func Backtrace(root *TreeNode, targetSum, curSum int) { if curSum == targetSum { re...

你的代码存在一些问题,主要是路径的递归计算没有正确处理。具体来说,当前节点的 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
}

修改与解释:

  1. Backtrace 函数:

    • 在进入函数时检查 root 是否为空。
    • 每次更新 curSum 为之前累积值加上当前节点的值。
    • 检查 curSum 是否等于 targetSum,如果相等则增加结果计数。
    • 遍历左右子树时,将更新后的 curSum 传递下去。
  2. pathSum 函数:

    • 定义一个内部的 dfs 函数,从每个节点开始执行深度优先搜索(DFS)。
    • 对于每一个以该节点为起点的路径,通过调用 Backtrace 来统计符合条件的路径数量。
    • 然后递归地遍历左、右子树,以确保所有可能的起点都被考虑到。

通过这样的修改,你可以得到正确答案,也能确保所有从任何一个父节点到其任意子孙结点的有效路径都会被统计到。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=19145

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?