[코딩인터뷰 완전정복] 4.12 합의 경로

Q : 각 노드의 값이 정수(음수 및 양수)인 이진 트리가 있다. 이때 정수의 합이 특정 값이 되도록 하는 경로의 개수를 세려고 한다. 경로가 꼭 루트에서 시작해서 말단 노드에서 끝날 필요는 없지만 반드시 아래로 내려가야 한다. 즉, 부모 노드에서 자식 노드로만 움직일 수 있다. 알고리즘을 어떻게 설계할 것인가?

 

1. Brute Force

모든 노드에 대해 해당 노드가 시작점이 되는 경로가 존재하는지 확인 한다.

1. 한 노드를 시작점으로 잡는다.
2. 시작점에서 깊이 우선 탐색을 이용해 탐색하며, 시작점에서 각 노드까지의 합을 기록한다.
3. 합이 특정 값이 되는 노드의 갯수를 샌다.
4. 모든 노드에 대해 반복한 후 그 수 모두 더해 반환한다.

 

2. 트리를 한번만 순회하는 방법

각 노드가 자신의 부모들로 부터 자신까지 더한 값에 대한 리스트를 가지고 있게 한다.

1. 루트에서 시작한다. (루트는 리스트에 자기 자신의 값이 들어있다.)
2. 리스트에 얻고자 하는 특정 값이 존재하면, 그 개수를 count에 더한다.
3. 자식노드를 탐색하며, 리스트를 넘겨준다.
4. 자식노드는 부모 노드의 리스트를 넘겨받아, 리스트의 각 원소에 자신의 값을 더하고, 자신의 값을 리스트의 마지막에 추가한다.
5. 2부터 반복하며, 모든 노드를 탐색한다. (부모부터 탐색하기만 하면, 탐색 순서는 상관없다.)
6. count를 반환한다.

 

예시)

다음과 같은 트리가 있다고 하자

루트 부터 탐색을 시작한다. 주어진 특정값은 0이라고 가정하겠다.

루트 리스트에 0의 개수는 0개이다.

왼쪽 부터 탐색을 시작한다.
-3 노드에서 리스트는 {1(-3), (-3)} => {-2, -3} 이고 0의 개수는 0개이다.
2 노드에서 리스트는 {-2(+2), -3(+2), (+2)} => {0, -1, 2} 이고 0의 개수는 1개이다. (total : 1)

모든 노드에 대해 반복한다.
0의 개수는 6개 이다. (total : 6)