Path Sum

Path sum

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

불러오는 중입니다...

given binary tree with integer value,

find the number of paths that sum to a given value.

Path does not need to start from the root.

 

solution:

Use partial sum

각 노드에 도착할 때마다,

노드에 도착할때까지 필요한 partial sum에  노드의 value를 추가하고

given value와 일치하는 partial sum이 있는지 확인한다.

 

leaf에서만 확인하는 경우, 경로가 중복해서 count 될 수 있다!