4.12 합의 경로

문제

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

 

접근법

해법 1 : 가능한 모든 경로를 다 살펴보면서 각 노드에서 재귀적으로 아래로 내려가면서 경로의 합을 구해나간다. 

하지만 TimeComplexity = O(NlogN)번 호출된다. 

 

해법2 : Running Sum을 이용한다 !

각 위치에서 러닝합을 알고있다면 runningSum(x) = runningSum (y) - targetNumber 일 것이다. 

우리는 경로의 갯수만 알면 되므로 runningSum을 key로 , runningSum을 만들 수 있는 갯수를 value로 가지는 해쉬테이블을 이용해서 문제를 해결해보자

DFS를 이용하여 각 노드를 방문할때마다 아래와 같은 방식을 넣는다.

1. runningSum을 알아야한다. 함수의 인자로 넘긴 뒤 node.value를 이용하여 바로 증가시킨다. 

2. runningSum - targetSum을 해쉬테이블에서 찾고 이 값은 전체 경로의 갯수를 의미한다. 이 값을 totalPaths에 대입한다.

3. 만약 runningSum == TargetSum 이라면 루트에서 시작하는 경로가 하나 더 있다는 뜻이다. totalPath를 증가시킨다.

4. runningSum을 해쉬테이블에 추가한다.(존재한다면 값 증가)

5. 왼쪽과 오른쪽으로 재귀적으로 탐색하면서 합이 targetSum인 경로를 구한다.

6. 재귀가 끝난 이후에는 해쉬테이블에서 runningSum의 값을 감소시킨다. 

 

def IncrementHash(pathCount, runningSum, delta):
    pathCount[runningSum] = pathCount.get(runningSum, 0) + delta
    if pathCount[runningSum] == 0 :
        del pathCount[runningSum]

def CountPathWithSum(root, targetSum, runningSum, pathCount):
    if root is None : return 0

    runningSum += root.data
    sum = runningSum - targetSum
    totalPath = pathCount.get(sum, 0)

    if runningSum == targetSum :
        totalPath +=1
    IncrementHash(pathCount, runningSum, 1)
    totalPath += CountPathWithSum(root.left, totalPath, runningSum, pathCount)
    totalPath += CountPathWithSum(root.right, totalPath, runningSum, pathCount)
    IncrementHash(pathCount, runningSum, -1)

    return totalPath

def Solution(root, targetSum):
    pathCount = {}
    return CountPathWithSum(root, targetSum, 0, pathCount)