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 协议》，转载必须注明作者和本文链接