https://leetcode-cn.com/problems/pa-sum-iii/
使用语言 Golang
先上正确的解决方案：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumChild(root *TreeNode, sum int) int {
if root == nil {
return 0
}
r := 0
if root.Val == sum {
r = 1
}
newSum := sum – root.Val
return r + sumChild(root.Left, newSum) + sumChild(root.Right, newSum)
}
func pathSum(root *TreeNode, sum int) int {
if root == nil {
return 0
}
return sumChild(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}
感悟：思路正确的程序，一定是最简洁直观的。
其实我最开始的思路就一直很正确，我把问题分解了一下，实际上就是求每个路径的和，其中和等于目标值的次数。下面是我第一次的提交：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumChild(root *TreeNode, targetSum int, sum int) int {
if root == nil {
return 0
}
if root.Val == sum {
return 1 + sumChild(root.Left, targetSum, targetSum) + sumChild(root.Right, targetSum, targetSum)
} else if root.Val > sum {
return 0 + sumChild(root.Left, targetSum, targetSum) + sumChild(root.Right, targetSum, targetSum)
}
newSum := sum – root.Val
return sumChild(root.Left, targetSum, newSum) + sumChild(root.Right, targetSum, newSum) + sumChild(root.Left, targetSum, sum) + sumChild(root.Right, targetSum, sum)
}
func pathSum(root *TreeNode, sum int) int {
return sumChild(root, sum, sum)
}
sumChild 的逻辑比较复杂，除了判断边界，我还判断了当前值与目标值的差异，这样其实是有问题的：并不是当前值比目标值大，就意味着整条路径都没有希望了。我也是在测试用例跑挂之后才想明白这个问题。
改了一版变成了这样：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumChild(root *TreeNode, targetSum int, sum int) int {
if root == nil {
return 0
}
if root.Val == sum {
return 1 + sumChild(root.Left, targetSum, targetSum) + sumChild(root.Right, targetSum, targetSum)
}
newSum := sum – root.Val
return sumChild(root.Left, targetSum, newSum) + sumChild(root.Right, targetSum, newSum) + sumChild(root.Left, targetSum, targetSum) + sumChild(root.Right, targetSum, targetSum)
}
func pathSum(root *TreeNode, sum int) int {
return sumChild(root, sum, sum)
}
这回只针对等值的情况做了处理，然而测试用例依然没跑过，挂在了下面这个输入上：
[1,null,2,null,3,null,4,null,5]
3
期望结果是 2，但是我跑出来是 3。想了想之后，我明白了：我的程序中发生了重复遍历！
就是同一条路径，遍历了多次。
很明显，我为了确保能够遍历到每一条路径，在 sumChild 中故意留了一个 targetSum，并用这个 targetSum 向每个子树进行递归。但实际上 sumChild 自己也在递归。拿左子树举个例子，左子树用新值递归了一遍，又用真实的目标值递归了一遍，对于左子树的左子树来讲，他一定会被递归到两次。
我忽然意识到，targetSum 这样一个很变扭的东西或许本身就不该出现，当你觉得一个东西很变扭的时候，可能他真的有问题。思考之后，我把程序改成了这样：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumChild(root *TreeNode, sum int) int {
if root == nil {
return 0
}
r := 0
if root.Val == sum {
r = 1
}
newSum := sum – root.Val
return r + sumChild(root.Left, newSum) + sumChild(root.Right, newSum)
}
func pathSum(root *TreeNode, sum int) int {
if root == nil {
return 0
}
return sumChild(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}
整个程序变的豁然开朗，pathSum 负责遍历每个子树，而 sumChild 负责计算子树上的可能路径的和。
很多时候 简洁 = 正确。