113.M 路径总和 II

Problem: 113. 路径总和 II

思路

与上一题判断是否存路径总和为目标值的路径相比，差别在于需要用两个变量来存储路径。

• paths：路径集合，作为返回结果

• path：存储一条路径（append到paths时需要深拷贝）

• 每次递归完左右子树之后，需要回退当前节点。

Code

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) [][]int {
	var paths [][]int
	var path []int
	helper(root, targetSum, path, &paths)
	return paths
}

func helper(root *TreeNode, targetSum int, path []int, paths *[][]int) {
	if root == nil {
		return
	}
	path = append(path, root.Val)
	targetSum -= root.Val
	if root.Left == nil && root.Right == nil && targetSum == 0 {
		// 注意这里需要深拷贝
		*paths = append(*paths, append([]int{}, path...))
	}

	helper(root.Left, targetSum, path, paths)
	helper(root.Right, targetSum, path, paths)
	// 回退当前节点
	path = path[0 : len(path)-1]
}