자바 코딩테스트 강좌, 트리 알아보기

트리는 프로그래밍에서 자주 사용되는 자료구조로, 노드와 간선으로 이루어진 연결 구조입니다. 각 노드는 데이터와 연결 정보를 가지며, 하나의 루트 노드를 가지며 자식 노드로 연결됩니다. 이 글에서는 트리의 기본 개념과 트리와 관련된 문제를 해결하는 방법을 알아보겠습니다.

트리의 기본 개념

트리는 다음과 같은 용어로 이루어져 있습니다:

  • 노드(Node): 데이터와 그 데이터를 연결하는 정보를 포함하는 구조입니다.
  • 루트 노드(Root Node): 트리의 최상위 노드입니다.
  • 부모 노드(Parent Node): 자식 노드를 갖는 노드입니다.
  • 자식 노드(Child Node): 부모 노드에 연결된 노드입니다.
  • 리프 노드(Leaf Node): 자식 노드가 없는 노드입니다.
  • 깊이(Depth): 루트 노드에서 특정 노드까지의 경로 길이입니다.
  • 높이(Height): 특정 노드에서 가장 깊은 리프 노드까지의 경로 길이입니다.

문제 정의

자바를 사용하여 다음과 같은 트리 관련 문제를 해결해봅시다. 주어진 이진 트리의 깊이를 구하는 문제입니다.

문제: 이진 트리의 깊이 구하기

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }
}

문제 해결 과정

1. 문제 이해하기

이 문제는 주어진 이진 트리를 순회하여 각각의 노드의 깊이를 계산하는 것입니다. 이때 깊이는 루트 노드에서 시작하여 특정 노드까지의 간선 수로 정의됩니다.

2. 해결 방법 선택하기

이 문제를 해결하기 위해 재귀적 방식으로 트리를 탐색하는 방법을 사용할 것입니다. 현재 노드가 null인 경우에는 깊이가 0임을 의미하며, 그렇지 않을 경우 왼쪽 서브트리와 오른쪽 서브트리의 깊이를 재귀 호출을 통해 구하고, 둘 중 큰 값을 선택하여 1을 더하는 방식으로 계산합니다.

3. 코드 작성하기

위 접근 방식을 통해 코드를 작성합니다.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public int maxDepth(TreeNode root) {
        // 기저 사례: 빈 노드일 때
        if (root == null) {
            return 0;
        }

        // 왼쪽과 오른쪽 서브트리의 깊이 재귀적으로 구하기
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        // 둘 중 큰 값에 1 더한 값을 반환
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

4. 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 트리 내의 노드 수를 의미합니다. 이는 모든 노드를 한 번씩 방문해야 하기 때문입니다.

5. 최종 코드 및 테스트

이제 완성된 코드를 테스트하여 올바르게 동작하는지 확인해봅시다.

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        Solution solution = new Solution();
        System.out.println("트리의 깊이는: " + solution.maxDepth(root)); // 출력: 3
    }
}

6. 결론

이번 강좌에서는 트리의 기본 개념과 이진 트리의 깊이를 구하는 알고리즘 문제를 다루어봤습니다. 재귀적 접근 방식이 이 문제를 효과적으로 해결할 수 있음을 알 수 있었습니다. 다양한 트리 문제를 해결하는 데 있어 이러한 기초 개념이 매우 중요하며, 더 복잡한 문제를 풀이하는 데 도움이 될 것입니다.

참고사항: 트리에 대한 이해도를 높이기 위해 다양한 형태의 트리 문제를 연습하시기 바랍니다. 특히, 이진 검색 트리, 균형 이진 트리 그리고 트리 순회 방법 등을 공부하면 좋습니다.

추가 자료