力扣（python3自用）2026.4.20

张开发
• 2026/4/21 10:20:13 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

力扣（python3自用）2026.4.20
最近没有刷力扣罪过主要是跑实验太累了今天做了一道题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, val0, leftNone, rightNone): # 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

更多文章