最近没有刷力扣，罪过，主要是跑实验太累了，今天做了一道题
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
思路：双dfs，外面那个负责看每个节点，每个节点的左子树，右子树上的路径数量之和，也就是当前节点的路径数量。里面dfs负责看路径上是否满足targetSum，主要是根据减法来做。每个dfs中重置一下count，表示当前节点的路径数量。
# 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: if not root: return 0 root_cnt = self.slove_path(root,targetSum) left_cnt = self.pathSum(root.left,targetSum) right_cnt = self.pathSum(root.right,targetSum) return root_cnt + left_cnt + right_cnt def slove_path(self,node,targetSum): if not node: return 0 count = 0 if targetSum == node.val: count += 1 remain = targetSum - node.val left_count = self.slove_path(node.left,remain) right_count = self.slove_path(node.right,remain) return count + left_count + right_count
