[LeetCode][Python3] 437. Path Sum III

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이라는 뜻이므로, 그 갯수만큼 정답을 증가시키는 것이다.