正文
leetcood学习笔记-437-路径总和③**
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目描述：
方法一：栈
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
count = 0
if root == None:
return count
stack = [(root,[root.val])]
while stack != []:
tree,number = stack.pop()
for i in number:
if i == sum:
count += 1
if tree.left:
stack.append((tree.left,[tree.left.val]+[_+tree.left.val for _ in number]))
if tree.right:
stack.append((tree.right,[tree.right.val]+[_+tree.right.val for _ in number]))
return count
方法二：
class Solution:
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
self.result = 0
self.sum = sum
current_sum_list = [] def current_sum(root, current_sum_list):
if root is not None:
for i in range(len(current_sum_list)):
current_sum_list[i] += root.val
if current_sum_list[i] == self.sum:
self.result += 1
current_sum_list.append(root.val)
if root.val == self.sum:
self.result += 1
# print(current_sum_list) current_sum(root.left, current_sum_list[:])
current_sum(root.right, current_sum_list[:]) current_sum(root, current_sum_list) return self.result
方法三：最快
class Solution(object):
def pathSum(self, root, sum):
from collections import defaultdict
lookup = defaultdict(int)
lookup[0] = 1
self.res = 0 def helper(root,curSum):
if not root:
return
curSum += root.val
self.res += lookup[curSum - sum]
lookup[curSum] += 1
helper(root.left,curSum)
helper(root.right,curSum)
lookup[curSum] -= 1
helper(root,0)
return self.res
