Path Sum III
这题给我的教训太深了,如果一道题相对太难太复杂,没有完整的思路,千万千万千万不要用过程化的方式写伪代码,这样是一直在满足特殊情况的修修补补,最后写出一堆垃圾代码只能删掉,先放宽条件,解决简单的问题,再一步步思考
还有,这种题要先画图 别做跳过去直接写伪代码的蠢事
how to solve it 应该是本很好的书,做里面的题?这本做完以后感觉可以去当老师了 XD
暗时间里提到的其他书也可以看下
func pathSum(root *TreeNode, sum int) int {
if root==nil {
return 0
}
res:=0
res+=findPath(root,sum)
if root.Left!=nil {
res+=pathSum(root.Left,sum)
}
if root.Right!=nil {
res+=pathSum(root.Right,sum)
}
return res
}
func findPath(node *TreeNode, sum int) int {
if node==nil {
return 0
}
res:=0
if sum-node.Val==0 {
res+=1
}
res+=findPath(node.Left,sum-node.Val)
res+=findPath(node.Right,sum-node.Val)
return res
}
pathSum(node,sum) {
if node nil {
return 0
}
res=0
res+=findPath(node,sum)
if left
res+=pathSum(left,sum)
if right
res+=pathSum(right,sum)
return res
}
findPath(node,sum) {
if node nil {
return 0
}
res=0
if sum-node.v==0 {
res+=1
}
res+=findPath(node,sum-node.v)
return res
}
错误的过程化思考方式
global res=0
findPathsIn(node,sum) {
if sum-node.v==0 {
res++
return
}
if sum-node.v<0 {
if node has left child {
findPathsIn(node.left,sum)
}
if node has right child {
findPathsIn(node.right,sum)
}
return
}
if sum-node.v>0 {
if node has left child {
findPathsIn(node.left,sum-node.v)
}
if node has right child {
findPathsIn(node.right,sum-node.v)
}
return
}
}
写出来的垃圾代码
本作品采用《CC 协议》,转载必须注明作者和本文链接