package leetcode import ( "github.com/halfrost/LeetCode-Go/structures" ) // TreeNode define type TreeNode = structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ // 解法一 带缓存 dfs func pathSum(root *TreeNode, targetSum int) int { prefixSum := make(map[int]int) prefixSum[0] = 1 return dfs(root, prefixSum, 0, targetSum) } func dfs(root *TreeNode, prefixSum map[int]int, cur, sum int) int { if root == nil { return 0 } cur += root.Val cnt := 0 if v, ok := prefixSum[cur-sum]; ok { cnt = v } prefixSum[cur]++ cnt += dfs(root.Left, prefixSum, cur, sum) cnt += dfs(root.Right, prefixSum, cur, sum) prefixSum[cur]-- return cnt } // 解法二 func pathSumIII(root *TreeNode, sum int) int { if root == nil { return 0 } res := findPath437(root, sum) res += pathSumIII(root.Left, sum) res += pathSumIII(root.Right, sum) return res } // 寻找包含 root 这个结点,且和为 sum 的路径 func findPath437(root *TreeNode, sum int) int { if root == nil { return 0 } res := 0 if root.Val == sum { res++ } res += findPath437(root.Left, sum-root.Val) res += findPath437(root.Right, sum-root.Val) return res }