공부하는 개발 블로그

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 될 수 있다!