给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。- 先序遍历每个节点，每个节点再先序遍历找目标值；
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: TreeNode, targetSum: int) -> int: # noqa
""""""
if root is None:
return 0
def dfs(x, rest):
if not x:
return 0
ans = 0 if x.val != rest else 1 # 如果相等说明，从头结点开始到该节点可以形成一条路径
# 继续遍历左右子树
rest -= x.val
ans += dfs(x.left, rest)
ans += dfs(x.right, rest)
rest += x.val # 回溯
return ans
# dfs 是一个先序遍历
ret = dfs(root, targetSum)
# pathSum 本身也是一个先序遍历，相当于对每个点都做一次 dfs
ret += self.pathSum(root.left, targetSum)
ret += self.pathSum(root.right, targetSum)
return retPython
# 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: TreeNode, targetSum: int) -> int:
from collections import defaultdict
self.prefix = defaultdict(int) # 保存前缀和
self.prefix[0] = 1
self.targetSum = targetSum
def dfs(x, preSum):
if not x: return 0
ret = 0
preSum += x.val
ret += self.prefix[preSum - targetSum]
self.prefix[preSum] += 1
ret += dfs(x.left, preSum)
ret += dfs(x.right, preSum)
self.prefix[preSum] -= 1
return ret
return dfs(root, 0)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: TreeNode, targetSum: int) -> int:
from collections import defaultdict
self.prefix = defaultdict(int) # 保存前缀和
self.prefix[0] = 1
self.targetSum = targetSum
def dfs(x, preSum):
if not x: return 0
ret = 0
preSum += x.val
ret += self.prefix[preSum - targetSum]
self.prefix[preSum] += 1
ret += dfs(x.left, preSum)
ret += dfs(x.right, preSum)
self.prefix[preSum] -= 1
return ret
return dfs(root, 0)
给定一个数组 A，试返回数组 B，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。
不能使用除法。详细描述
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
提示：
所有元素乘积之和不会溢出 32 位整数
a.length <= 100000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。-
双向构建前缀积（左→右、右→左），示例：
l = [1, a1, a1a2, a1a2a3] r = [a2a3a4, a3a4, a4, 1] s = [l[0] * r[0] for i in range(len(a))]
Python
class Solution:
def constructArr(self, a: List[int]) -> List[int]:
l = [1]
for x in a[:-1]:
l.append(l[-1] * x)
# print(l)
r = [1]
for x in a[::-1][:-1]:
r.append(r[-1]*x)
r = r[::-1]
# print(r)
return [l[i] * r[i] for i in range(len(a))]Python：空间优化
- 实际上在求 s 的时候可以同步求前缀积，换言之，可以节省一组前缀积（这里优化掉
l）；
class Solution:
def constructArr(self, a: List[int]) -> List[int]:
r = [1] * len(a)
for i in range(len(a) - 1, 0, -1):
r[i - 1] = r[i] * a[i]
# print(r)
pre = 1
for i, x in enumerate(a):
r[i] *= pre
pre *= x
return r