LeetCode-437.路径总和 III - sheep44044的小站

二叉树#

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

1
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
2
输出：3
3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

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

递归的解法

思路：这题其实看过 113. 路径总和 II 和 112. 路径总和 的题目后，比较一下就可以发现本题的答案就是子节点的递归 + 根节点的路径数目，由此写出两个递归即可

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
    if root == nil {
11
        return 0
12
    }
13

14
    res := rootsum(root, targetSum)
15

16
    res += pathSum(root.Left, targetSum)
17
    res += pathSum(root.Right, targetSum)
18

19
    return res
20
}
21

22
func rootsum(node *TreeNode, targetSum int) int {
23
    if node == nil {
24
        return 0
25
    }
26

27
    count := 0
28
    if node.Val == targetSum {
29
        count++
30
    }
31

32
    count += rootsum(node.Left, targetSum-node.Val)
33
    count += rootsum(node.Right, targetSum-node.Val)
34

35
    return count
36
}