<aside> 💬 lv1, 데이터 구조

이진 트리에서의 경로 합 계산

문제 설명

딕셔너리 형태로 주어진 이진 트리에서, 모든 루트 노드부터 리프 노드까지의 경로에 있는 노드의 값의 합을 계산하는 함수를 작성해주세요. 이진 트리는 딕셔너리로 표현되며, 각 노드는 자신의 값과 왼쪽 자식, 오른쪽 자식을 가리키는 키를 가집니다. 리프 노드는 자식이 없는 노드입니다.

예를 들어, 아래와 같은 이진 트리가 주어집니다.

     1
    / \\\\
  2   3
 / \\\\
4  5

이 트리는 다음과 같은 딕셔너리로 표현될 수 있습니다: {"value": 1, "left": {"value": 2, "left": {"value": 4}, "right": {"value": 5}}, "right": {"value": 3}}.

루트 노드부터 리프 노드까지의 경로는 [1, 2, 4], [1, 2, 5], [1, 3]이며, 이들 경로의 합은 각각 7, 8, 4입니다.

제한 사항

• 트리의 노드 수는 1 이상 10,000 이하입니다.
• 각 노드의 값은 -10,000 이상 10,000 이하의 정수입니다.

입출력 예

입출력 설명

주어진 딕셔너리 형식의 이진 트리에서 모든 루트 노드부터 리프 노드까지의 경로의 합을 계산하여 리스트로 반환합니다.

</aside>

풀이 1. 재귀 함수를 사용한 모든 노드 방문

def solution(data):
    tree = data["tree"] **#1 기본 조건 체크**
    if not tree:
        return []

    def find_sums(node, current_sum): **#2 내부 함수find_sums**
        if not node: **#3 더 이상 탐색할 노드가 없을 때**
            return []
        if not node.get("left") and not node.get("right"): **#4 리프 노드인지 확인**
            return [current_sum + node["value"]]
        return find_sums(node.get("left"), current_sum + node["value"]) + find_sums(node.get("right"), current_sum + node["value"]) **#5 리프 노드가 아닐 때**

    return find_sums(tree, 0)

단계별 풀이 전략

1. 기본 조건 체크

   이 부분은 주어진 data가 비어있거나 None인 경우를 처리합니다.

2. 내부 함수find_sums

   이 함수는 재귀 적으로 트리를 탐색하며, 각 루트-리프 경로의 합을 계산합니다.

3. 더 이상 탐색할 노드가 없을 때

   이 조건은 현재 노드가 None인 경우를 처리합니다. 즉, 더 이상 탐색할 노드가 없을 때 빈 리스트를 반환합니다.

4. 리프 노드인지 확인

   이 조건은 현재 노드가 리프 노드인지 확인합니다. 리프 노드는 왼쪽과 오른쪽 자식이 모두 없는 노드입니다. 리프 노드인 경우, 현재까지의 합 current_sum + node["value"]을 리스트에 담아 반환합니다.

5. 리프 노드가 아닐 때

   리프 노드가 아닌 경우, 왼쪽 자식과 오른쪽 자식에 대해 find_sums 함수를 재귀 적으로 호출합니다. 각 호출에서 현재 노드의 값node["value"] 을 current_sum에 추가하여 전달합니다. 이렇게 해서 왼쪽과 오른쪽 서브 트리 각각에서 계산된 경로의 합의 리스트를 합쳐서 반환합니다. 최종적으로,find_sums함수는 모든 리프 노드에 대한 경로의 합을 포함하는 리스트를 반환합니다.

알아 둬야 할 개념

이 풀이 방법은 주어진 트리의 모든 노드를 방문하여 처리합니다. 트리의 각 노드를 재귀 적으로 탐색합니다. 이 코드의 시간 복잡도는 O(N) 입니다. N은 트리의 노드 수이고, 노드가 늘어날 때마다 시간은 선형 적으로 증가합니다. 재귀 함수는 문법적으로 어려운 점은 없지만 흐름을 놓치지 않고 따라갈 수 있어야 한다고 했습니다.

아래의 데이터로 흐름을 따라가 보겠습니다.

{"value": 1, "left": {"value": 2, "left": {"value": 4}, "right": {"value": 5}}, "right": {"value": 3}}

• 초기 노드는 루트 노드(value: 1)입니다.

  루트 노드는 왼쪽(left)과 오른쪽(right) 자식 노드를 가지고 있으므로, 리프 노드가 아닙니다. 따라서, 왼쪽 자식 노드에 대한 find_sums 함수와 오른쪽 자식 노드에 대한 find_sums 함수를 재귀 적으로 호출합니다.

• 왼쪽 자식 노드 처리 (value: 2)

  왼쪽 자식 노드(값 2)에 대해 find_sums 함수를 호출합니다. 이 노드는 자신의 왼쪽(left, 값 4)과 오른쪽(right, 값 5) 자식 노드를 가지고 있습니다. 리프 노드가 아니므로, 해당 자식 노드들에 대해 재귀 적으로 find_sums 함수를 호출합니다.

  • 왼쪽 자식 노드(값 4)는 리프 노드입니다. 따라서, [current_sum + node["value"]]를 반환합니다. 이때, current_sum은 1(루트 노드의 값) + 2(현재 노드의 값) = 3입니다. 최종적으로 [7]을 반환합니다.
  • 오른쪽 자식 노드(값 5)도 리프 노드이므로, 마찬가지로 [current_sum + node["value"]]를 반환합니다. 이때, current_sum은 1 + 2 = 3입니다. 최종적으로 [8]을 반환합니다.

  따라서, 왼쪽 자식 노드(값 2)에 대한 find_sums 호출은 [7, 8]을 반환합니다.

• 오른쪽 자식 노드 처리 (value: 3)

  오른쪽 자식 노드(값 3)에 대해 find_sums 함수를 호출합니다. 이 노드는 리프 노드이므로, 바로 [current_sum + node["value"]]를 반환합니다. 이때, current_sum은 1(루트 노드의 값)입니다. 최종적으로 [4]를 반환합니다.

• 최종

  루트 노드에 대한 find_sums 함수 호출은 왼쪽 자식 노드의 결과 [7, 8]과 오른쪽 자식 노드의 결과 [4]를 합친 [7, 8, 4]를 반환합니다.

풀이 2. 재귀 함수를 사용한 모든 노드 방문

def solution(data):
    tree = data["tree"] **#1 기본 조건 체크**
    paths_sum = []

    def bin_tree(node, current_sum=0): **#2 내부 함수 bin_tree**
        if not node: **#3 현재 노드가 없다면**
            return
        current_sum += node["value"] **#4 현재 노드가 있다면**
        if "left" not in node and "right" not in node: **#5 현재 노드가 리프 노드 라면**
            paths_sum.append(current_sum)
            return
        if "left" in node: **#6 현재 노드의 left 키가 있다면**
            bin_tree(node["left"], current_sum)
        if "right" in node: **#7 현재 노드의 right 키가 있다면**
            bin_tree(node["right"], current_sum)
            
    bin_tree(tree)

    return paths_sum **#8 모든 경로의 합 반환**