[Leetcode] 437. Path Sum III

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

---

이진 트리와 targetSum이 주어지면 경로의 노드들 값의 합이 targetSum과 같은 경로들의 수를 구하라.

---

백트래킹.

트리를 탐색하면서 탐색한 노드들의 val의 합의 개수를 map에 저장한다.

[그림 1]

탐색하면서 이때까지의 합(sum)에서 targetSum을 뺀 값의 개수들의 합이 정답이 된다.

[그림 1]에서는 테이블들의 빨간색 셸들이 이에 해당하여 정답은 3이 된다.

 

시간복잡도는 O(N). N = 노드 수

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/437.%20Path%20Sum%20III.cpp