Problem :

https://leetcode.com/problems/path-sum-iii/description/


My Solution :

# 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, target):
self.target = target
self.result = 0
self.cache = {0: 1}
self.count_path(root, 0)
return self.result

def count_path(self, root, total):
if root:
total += root.val
self.result += self.cache.get(total - self.target, 0)
self.cache[total] = self.cache.get(total, 0) + 1
self.count_path(root.left, total)
self.count_path(root.right, total)
self.cache[total] -= 1


Comment :

이 문제는 좋은 방법이 생각나지 않아서 Discuss를 참조하였다. 아이디어의 핵심은 root node로부터 각 node까지의 총 합을 cache에 기록하고, 총 합에서 target을 뺀 값이 cache에 존재한다면 거기서부터 해당 node까지의 총 합이 target이라는 뜻이므로, 그 갯수만큼 정답을 증가시키는 것이다.