코딩 테스트 대비: 이진 트리의 최대 깊이 구하기(C#)

안녕하세요, GameLabMaster입니다! 코딩 테스트 대비 두 번째 포스팅에서는 이진 트리의 최대 깊이를 구하는 문제를 다루겠습니다. 이 문제는 코딩 테스트에서 자주 나오는 중급 정도의 문제로, 트리 구조에 대한 이해가 필요합니다.

 

문제
주어진 이진 트리의 최대 깊이를 구하세요. 이진 트리의 최대 깊이란 루트 노드부터 가장 먼 리프 노드까지의 거리를 의미합니다.

예시:

 

    3
   / \
  9  20
    /  \
   15   7

 

최대 깊이: 3

 

풀이
이 문제는 재귀적인 방법을 사용하여 해결할 수 있습니다. 각 노드에서 왼쪽과 오른쪽 자식 노드의 깊이를 구한 후, 둘 중 더 큰 값을 선택하고 현재 노드의 깊이 1을 더해주면 됩니다. 이 과정을 루트 노드부터 시작하면 최대 깊이를 구할 수 있습니다.

 

먼저, 이진 트리의 노드를 표현하기 위해 TreeNode 클래스를 정의하겠습니다.

 

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 int MaxDepth(TreeNode root) {
        // 기저 조건: 노드가 비어있으면 깊이 0 반환
        if (root == null) {
            return 0;
        }

        // 왼쪽과 오른쪽 자식 노드의 깊이를 재귀적으로 구함
        int leftDepth = MaxDepth(root.left);
        int rightDepth = MaxDepth(root.right);

        // 둘 중 더 큰 깊이를 선택하고 현재 노드의 깊이 1을더해줍니다.
        return Math.Max(leftDepth, rightDepth) + 1;
    }
}

 

이 메서드는 재귀적으로 트리를 탐색하며 깊이를 계산합니다. 기저 조건을 이용하여 빈 노드에 도달했을 때는 깊이 0을 반환하게 합니다. 이후, 왼쪽과 오른쪽 자식 노드의 깊이를 구하고 둘 중 더 큰 값을 선택하여 현재 노드의 깊이 1을 더해줍니다.

 

이제 주어진 이진 트리를 생성하고, 최대 깊이를 구하는 메서드를 호출해보겠습니다.

 

public static void Main(string[] args) {
    TreeNode root = new TreeNode(3);
    root.left = new TreeNode(9);
    root.right = new TreeNode(20);
    root.right.left = new TreeNode(15);
    root.right.right = new TreeNode(7);

    Solution solution = new Solution();
    int maxDepth = solution.MaxDepth(root);
    Console.WriteLine("최대 깊이: " + maxDepth);
}

 

위 예제에서는 주어진 이진 트리를 생성하고, Solution 클래스의 MaxDepth 메서드를 호출하여 최대 깊이를 구한 뒤 출력하였습니다. 실행 결과, "최대 깊이: 3"이 출력됩니다.

 

이상으로 오늘의 코딩 테스트 대비 포스팅을 마치겠습니다. 다음 포스팅에서도 더 유용한 정보를 드릴 것입니다. 그럼, 즐거운 코딩 되세요!