【python

2023-01-11 17:32| 来源: 网络整理| 查看: 265

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

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

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def pathSum(self, root: TreeNode, sum: int) -> int: if not root: return 0 res=0 #如果当前值等于sum，结果加1 if root.val == sum: res+=1 #若等于sum，则有两种请情况 #第一种情况，包含该节点，继续遍历 res+=self.helper(root.left,sum-root.val) res+=self.helper(root.right,sum-root.val) #第二种情况，不包含该节点，继续遍历 res+=self.pathSum(root.left,sum) res+=self.pathSum(root.right,sum) return res def helper(self,root,target): if not root: return 0 #这里必须先声明tmp=0 tmp=0 if root.val == target: tmp+=1 #继续遍历 tmp+=self.helper(root.left,target-root.val) tmp+=self.helper(root.right,target-root.val) return tmp

【本文地址】

【python

【python

今日新闻

推荐新闻