437. 路径总和 III
已解答
中等
相关标签
相关企业
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
简单算法是遍历一遍所有节点，然后去搜索这个节点开始的所有路径的总和是不是符合条件
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def pathSum(self, root, targetSum):
"""
:type root: Optional[TreeNode]
:type targetSum: int
:rtype: int
"""
self.ret = 0
if root:
queue = [root]
else:
queue=[]
def dfs(tmp,targetSum):
if tmp==None:
return 0
else:
if tmp.val == targetSum:
self.ret+=1
dfs(tmp.left,targetSum-tmp.val)
dfs(tmp.right,targetSum-tmp.val)
while len(queue):
tmp = queue[0]
x1 = dfs(tmp,targetSum)
del queue[0]
if tmp.left:
queue.append(tmp.left)
if tmp.right:
queue.append(tmp.right)
return self.ret
难的办法没看懂
