ZBLOG

var result int func Backtrace(root *TreeNode, targetSum, curSum int) { if root == nil { return } curSum += root.Val if curSum == targetSum { result++ } Backtrace(root.Left, targetSum, 0) Backtrace(root.R...

你的代码中出现重复路径计数的问题,主要是因为在递归调用时,你对左子树和右子树的遍历方法不正确。

在每次递归中,当你进入一个节点时,你应该从当前节点开始计算路径,而不是总是从根节点或子树的根开始。在你的代码里,调用 Backtrace 方法的时候,对左右子树都传入了 0 作为 curSum。这样做会导致在每次进入新的子树时重新计算路径和,从而漏掉一些有效的路径。

下面是修正后的代码:

  1. var result int
  2. func Backtrace(root *TreeNode, targetSum, curSum int) {
  3. if root == nil {
  4. return
  5. }
  6. curSum += root.Val
  7. // Check if the current path sum equals to target sum
  8. if curSum == targetSum {
  9. result++
  10. }
  11. // Continue traversing down the tree, carrying along the current sum
  12. Backtrace(root.Left, targetSum, curSum)
  13. Backtrace(root.Right, targetSum, curSum)
  14. }
  15. func pathSum(root *TreeNode, targetSum int) int {
  16. if root == nil {
  17. return 0
  18. }
  19. // Reset result for each invocation of pathSum
  20. result = 0
  21. // Start backtracking from the current node and also check paths from left and right children.
  22. Backtrace(root, targetSum, 0)
  23. // Recursively call pathsum for left and right subtrees to ensure all paths are counted.
  24. pathSum(root.Left, targetSum)
  25. pathSum(root.Right, targetSum)
  26. return result
  27. }

修复点:

  1. 遍历逻辑:移除了将 curSum 重置为 0 的调用,这样我们可以保持当前路径的累加值。
  2. 递归调用:添加了对左、右子树的额外递归调用,确保每个节点都被当作起点来检查可能的路径。

这样,每次都会从当前节点继续向下查找所有可能的路径,并统计符合条件的路径数量。这就能避免因为重置 curSum 而导致的漏计问题。


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

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

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

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

联系我们

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

微信号:3007537140

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

关注我们
x

注册

已经有帐号?