C# 코딩테스트 강좌, 이진 트리

문제 설명

주어진 이진 트리의 모든 경로 합을 구하는 함수를 작성하세요.
경로는 루트에서 잎(leaf) 노드까지의 경로이며, 이 경로에 포함되는 모든 노드의 값의 합이 이 경로의 합입니다.

입력 형식

  • 입력: 이진 트리의 루트 노드(root)는 TreeNode 클래스의 인스턴스입니다.

출력 형식

  • 출력: 모든 경로의 합을 담은 리스트(List)를 반환합니다.

예시

            입력: [1, 2, 3]
            출력: [3, 4]

이 예시에서, 경로는 1 -> 2와 1 -> 3입니다. 첫 번째 경로의 합은 3이며, 두 번째 경로의 합은 4입니다.

문제 분석

이 문제를 해결하기 위해서는 이진 트리를 탐색할 수 있는 방법이 필요합니다.
대표적인 알고리즘으로는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.
이 문제에서는 DFS가 더 적합합니다. DFS를 통해 각 경로의 노드를 탐색하며 경로의 총합을 계산합니다.

해결 전략

1. 재귀 함수를 통해 각 노드를 방문합니다.
2. 현재 노드의 값을 경로의 합에 추가합니다.
3. 현재 노드가 잎 노드인지 확인합니다.
4. 잎 노드라면 현재까지의 합을 리스트에 추가합니다.
5. 자식 노드가 있다면 자식 노드를 재귀적으로 탐색합니다.
6. 탐색이 끝난 후에는 부모 노드로 돌아가기 위해 경로의 합에서 현재 노드의 값을 제거합니다.

C# 코드 구현

아래는 이진 트리의 모든 경로 합을 구하는 C# 코드입니다. 


using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public IList PathSum(TreeNode root) {
        List result = new List();
        FindPaths(root, 0, result);
        return result;
    }

    private void FindPaths(TreeNode node, int currentSum, List result) {
        if (node == null) {
            return;
        }

        currentSum += node.val;

        // Check if we are at a leaf node
        if (node.left == null && node.right == null) {
            result.Add(currentSum);
        } else {
            // Traverse the left and right subtree
            FindPaths(node.left, currentSum, result);
            FindPaths(node.right, currentSum, result);
        }
    }
}

코드 설명

TreeNode 클래스: 이진 트리의 각 노드를 표현하는 클래스입니다.
각 노드는 정수 값(val), 왼쪽 자식(left), 오른쪽 자식(right)을 가질 수 있습니다.

Solution 클래스: 이진 트리의 경로 합을 계산하는 메소드를 포함하는 클래스입니다.
PathSum 메소드는 재귀적으로 노드를 탐색하는 FindPaths 메소드를 호출합니다.

  • PathSum 메소드: 주어진 이진 트리를 입력으로 받아, 모든 경로의 합을 리스트로 반환합니다.
  • FindPaths 메소드: 현재 노드와 현재까지의 경로 합을 인자로 받아서 재귀적으로 탐색합니다.
    잎 노드에 도달하면 현재 경로의 합을 리스트에 추가합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다. N은 트리의 노드 수입니다.
모든 노드를 한 번씩 방문하기 때문입니다. 공간 복잡도 또한 O(H)입니다. H는 트리의 높이입니다.
재귀 호출에 사용되는 스택 공간을 고려한 것입니다.

결론

이 문제를 통해 이진 트리의 탐색 방법과 재귀적인 접근법을 이해할 수 있습니다.
다양한 이진 트리 문제를 풀기 위해 이러한 기법을 익혀 두는 것이 중요합니다.
충분한 연습을 통해 이진 트리와 그 활용 방법에 익숙해지길 바랍니다.