113. Path Sum II

找出一棵二叉树所有的从根节点到某一叶子节点的路径，该路径上所有节点的和为一个特定值。

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

}