LeetCode-113. 路径总和 II - sheep44044的小站

二叉树#

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

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

示例 1：

1
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
2
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

1
输入：root = [1,2,3], targetSum = 5
2
输出：[]

示例 3：

1
输入：root = [1,2], targetSum = 0
2
输出：[]

解法

原本只是想先做一下路径总和 I 和路径总和 II，为路径总和 III铺垫一下的，没想到还涉及到了回溯，更不会做了☹️，不过最终还是理解了

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func pathSum(root *TreeNode, targetSum int) [][]int {
10
    var res [][]int
11
    var path []int
12

13
    var dfs func(*TreeNode, int)
14
    dfs = func(node *TreeNode, sum int) {
15
        if node == nil {
16
            return
17
        }
18

19
        path = append(path, node.Val)
20
        sum -= node.Val
21

22
        if node.Left == nil && node.Right == nil && sum == 0 {
23
            tmp := make([]int, len(path))
24
            copy(tmp, path)
25
            res = append(res, tmp)
26
        } else {
27
            dfs(node.Left, sum)
28
            dfs(node.Right, sum)
29
        }
30

31
        path = path[:len(path)-1]
32
    }
33

34
    dfs(root, targetSum)
35
    return res
36
}