LeetCode热题100-路径总和 III

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

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

示例 1：

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

思路

• 双重递归：
  • 外层：遍历每一个节点作为起点
  • 内层：从该起点向下遍历，统计符合和的路径数

class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int: if not root: return 0 def dfs(node, cur): if not node: return 0 cnt = 0 cur += node.val if cur == targetSum: cnt += 1 cnt += dfs(node.left, cur) cnt += dfs(node.right, cur) return cnt return dfs(root, 0) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)