leetcode_437

Golang:

思路：这题没有好的思路，双重递归吧，第一次拿到所有节点，第二次对所有节点进行递归，看看有没有路径符合题目要求。这里讲下我最初的思路：我最开始想的是，把每一条从根节点到叶子节点的路径都提取出来（以数组的形式），然后去对数组做处理，这样会不会效率高一些。后面思考不难发现，这样如果可以实现，会有很多重复的路径被算进总和。所以，这题可能就只剩下暴力的求解思路了。

再插一句，递归这东西，在树结构里真的是无往不利。

代码如下：

func pathSum(root *TreeNode, sum int) int {
    if root==nil {
        return 0
    }
    var nodes []TreeNode
    traverse(root,&nodes)
    res:=0
    for _,v:=range nodes{
        findKinTree(&v,0,sum,&res)
    }
    return res
}
func traverse(root *TreeNode,nodes *[]TreeNode) {
    if root!=nil {
        *nodes=append(*nodes, *root)
        if root.Left!=nil {
            traverse(root.Left,nodes)
        }
        if root.Right!=nil {
            traverse(root.Right,nodes)
        }
    }
}
func findKinTree(root *TreeNode,sum int,k int,res *int)  {
    if root!=nil {
        sum=sum+root.Val
        if sum==k {
            *res++
        }
        if root.Left!=nil {
            findKinTree(root.Left,sum,k,res)
        }
        if root.Right!=nil {
            findKinTree(root.Right,sum,k,res)
        }
    }
}

有疑问加站长微信联系（非本文作者）