题目
437. 路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
提示:
- 二叉树的节点个数的范围是 [0,1000]
- -109 <= Node.val <= 109
- -1000 <= targetSum <= 1000
我的代码（Python）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
def sumInner(root: Optional[TreeNode], targetSum: int, currTar: Optional[int]):
if root is None:
return 0
if currTar is None:
return (1 if root.val == targetSum else 0) + sumInner(root.left, targetSum, None) + sumInner(root.right, targetSum, None) + sumInner(root.left, targetSum, root.val) + sumInner(root.right, targetSum, root.val)
else:
return (1 if root.val == targetSum - currTar else 0) + sumInner(root.left, targetSum, currTar + root.val) + sumInner(root.right, targetSum, currTar + root.val)
return sumInner(root, targetSum, None)点评
时间复杂度不好，但是间复杂度还不错。
想法很直接，递归计算即可。需要注意的是重复计算。我一开始没有区分是否是从0开始重新计算，每一个结点都写成左 / 右树中的重新计数 + 左 / 右树中的加上当前结点的路径计数，结果有重复计算，结果是错误的。
实际上这和官方解法的第一种，深度优先搜索是一样的。
官方解法第二种前缀和，理解起来有点难度，不过明显其中借鉴了在数组中求指定和（leetcode 15 三数之和）的思想，对比起来看就比较容易理解了。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog