剑指 Offer 34. 二叉树中和为某一值的路径

mid

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

叶子节点是指没有子节点的节点。

DFS

每个递归维护一个数组，保存历史路径上的节点值；每次查到底，发现路径和满足要求就将数组添加到结果中。

注意 road 是一个切片，底层是指针，添加到 res 中时需要深拷贝

 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
29
30
func sum(nums []int) (sum int) {
	for _, num := range nums {
		sum += num
	}
	return
}

func pathSum(root *TreeNode, target int) [][]int {
	res := make([][]int, 0)
	var backtracking func(root *TreeNode, road []int)
	backtracking = func(root *TreeNode, road []int) {
		if root == nil {
			return
		}

		road = append(road, root.Val) // 在这里其实已经生成一个新slice了
       
		if sum(road) == target && root.Left == nil && root.Right == nil {
			// 到叶子节点 且路径和等于目标值
			tmp := make([]int, len(road)) // 拷贝切片
			copy(tmp, road)
			res = append(res, tmp)
			return
		}
		backtracking(root.Left, road)
		backtracking(root.Right, road)
	}
	backtracking(root, []int{})
	return res
}

回溯函数还可以传值，road 由一个变量统一维护：

 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
func pathSum(root *TreeNode, target int) [][]int {
	res := make([][]int, 0)
	road := make([]int, 0)
	var backtracking func(root *TreeNode, leftVal int) // leftVal 剩余的值
	backtracking = func(root *TreeNode, leftVal int) {
		if root == nil {
			return
		}

		road = append(road, root.Val)
		defer func() {
			road = road[:len(road)-1] // 收回最后一步
		}()

		leftVal -= root.Val
		if leftVal == 0 && root.Left == nil && root.Right == nil {
			// 到叶子节点 且路径和等于目标值
			res = append(res, append([]int{}, road...)) // 拷贝 因为road唯一 会不断变化
			return
		}
		backtracking(root.Left, leftVal)
		backtracking(root.Right, leftVal)
	}
	backtracking(root, target)
	return res
}

可以加个减枝条件：和已经大于 target 则停止检索