437.路径总和III
437.路径总和III
题解
题目：给一个二叉树，和一个target，求从上到下的路径，有几条路径的路径和=target，路径可以不包含根节点，叶子节点，但是路径要从上到下，连续。
思路：
- 双重递归
题目意思就是说可以不包括父节点 1.那么就有两种情况，包括和不包括 2.dfs：计算包含当前节点，并递归左右子树 3.pathSum：包含父节点进入dfs，不包含父节点进入左右子树的pathSum
- 前缀和
1.我们知道遍历树是天然从上往下的 2.在遍历的过程中计算前缀和 3.前n个节点前缀和 - 前n-i 个节点前缀和 = target 前n个节点前缀和-target=前n-i个节点前缀和 4.用map存前缀和，计数同一个前缀和的数量，计算第三步 5.回溯前缀和（左子树的前缀和，不能给右子树用） 6.初始化mp[0]=1,什么都不选的时候，空路径。 有可能：根节点开始的路径-target=空路径
代码
func pathSum(root *TreeNode, targetSum int) int { if root == nil { return 0 } res := dfs(root, targetSum) res += pathSum(root.Left, targetSum) res += pathSum(root.Right, targetSum) return res } func dfs(root *TreeNode, targetSum int) int { if root == nil { return 0 } ans := 0 if targetSum-root.Val == 0 { ans++ } ans += dfs(root.Left, targetSum-root.Val) ans += dfs(root.Right, targetSum-root.Val) return ans }
type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func pathSum(root *TreeNode, targetSum int) int { preFix := make(map[int]int) preFix[0] = 1 //防止根节点是targetSum时找不到 res := 0 var dfs func(root *TreeNode, cur int) dfs = func(root *TreeNode, cur int) { if root == nil { return } cur += root.Val res += preFix[cur-targetSum] //cur-x=target---->cur到x之间的节点总和等于target preFix[cur]++ dfs(root.Left, cur) dfs(root.Right, cur) preFix[cur]-- } dfs(root, 0) return res }
