找出一棵二叉树所有的从根节点到某一叶子节点的路径，该路径上所有节点的和为一个特定值。
Python:
class Solution:
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
# 6 star, dfs
# 就是dfs计算所有的路径和，有符合要求的就将路径加到结果集中
if not root:
return []
rs = []
self.dfs(sum-root.val, root, [root.val], rs)
return rs
def dfs(self, gap, node, path, rs):
if not node.left and not node.right and gap == 0:
rs.append(path)
return
if node:
if node.left:
self.dfs(gap-node.left.val, node.left, path + [node.left.val], rs)
if node.right:
self.dfs(gap-node.right.val, node.right, path + [node.right.val], rs)
Go:
func pathSum(root *TreeNode, sum int) [][]int {
ret := [][]int{}
if root == nil {return ret}
ret = dfs(root, 0, sum, []int{}, ret)
return ret
}
func dfs(node *TreeNode, curSum int, sum int, path []int, ret[][]int) [][]int{
if node.Right == nil && node.Left == nil {
curSum += node.Val
path = append(path, node.Val)
if curSum == sum {
temp := make([]int, len(path)) // 注意，这里拷贝了一份路径，然后放入结果里
copy(temp, path)
ret = append(ret, temp)
}
return ret
}
if node.Left != nil {
ret = dfs(node.Left, curSum+node.Val, sum, append(path, node.Val), ret)
}
if node.Right != nil {
ret = dfs(node.Right, curSum+node.Val, sum, append(path, node.Val), ret)
}
return ret
}