자바 코딩테스트 강좌, 이진 트리

문제 설명

이 문제에서는 이진 트리의 각 노드에 대해 값을 저장하고, 특정 값을 가진 노드를 찾아 이진 트리에서의 높이를 반환하는 알고리즘을 작성해야 합니다. 주어진 이진 트리는 다음과 같은 형태로 정의됩니다:

        class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }

문제: 이진 트리의 특정 값에 대한 높이 계산

주어진 이진 트리의 루트 노드와 특정 값 target이 주어진다. 이진 트리에서 target의 노드의 높이를 반환하라. 노드의 높이는 해당 노드에서 리프 노드까지의 가장 긴 경로의 길이로 정의된다. 만약 목표값을 가진 노드가 없으면 -1을 반환한다.

입력

TreeNode root: 이진 트리의 루트 노드
int target: 탐색할 값

출력

target의 높이, target을 찾을 수 없는 경우 -1

해결 방법

이 문제를 해결하기 위해서는 먼저 이진 트리의 높이를 계산하는 알고리즘을 이해하고 구현할 필요가 있습니다. 깊이 우선 탐색(DFS) 방식으로 트리를 탐색하면서, 목표한 값과 일치하는 노드를 찾고, 해당 노드의 높이를 반환하도록 설계합니다.

단계별 풀이

이진 트리의 구조 이해하기: 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조입니다. 각 노드는 데이터를 저장하고 있습니다.
깊이 우선 탐색(DFS) 구현: 재귀적으로 데이터를 탐색하며, 목표 노드를 찾도록 합니다.
높이 계산하기: 목표 노드를 찾으면 그 노드에서 리프까지의 최대 깊이를 계산합니다.
결과 반환: 목표 노드를 찾으면 그 높이를 반환하고, 찾지 못하면 -1을 반환합니다.

자바 코드 구현

        public class Solution {
            public int findHeight(TreeNode root, int target) {
                return findNodeHeight(root, target, 0);
            }

            private int findNodeHeight(TreeNode node, int target, int depth) {
                if (node == null) {
                    return -1; // 노드가 없으면 -1 반환
                }
                
                // 현재 노드가 목표 노드인 경우
                if (node.val == target) {
                    return getHeight(node);
                }
                
                // 리프 노드가 아닐 경우 자식 노드 탐색
                int leftHeight = findNodeHeight(node.left, target, depth + 1);
                int rightHeight = findNodeHeight(node.right, target, depth + 1);

                // 왼쪽 노드에서 목표 노드를 찾았다면 그 높이를 반환
                if (leftHeight != -1) {
                    return leftHeight;
                }
                // 오른쪽 노드에서 목표 노드를 찾았다면 그 높이를 반환
                return rightHeight;
            }

            private int getHeight(TreeNode node) {
                if (node == null) return -1; // 리프 노드의 경우 깊이는 -1
                
                // 왼쪽과 오른쪽 서브트리의 깊이를 재귀적으로 계산
                int leftHeight = getHeight(node.left);
                int rightHeight = getHeight(node.right);
                
                // 현재 노드에서 리프 노드까지의 최대 깊이 반환
                return Math.max(leftHeight, rightHeight) + 1;
            }
        }

코드 설명

위의 코드에서 findHeight 메서드는 루트 노드와 목표값을 인자로 받아 노드를 탐색합니다. findNodeHeight는 재귀적으로 각 노드를 탐색하며 목표한 값을 찾아 그 높이를 계산합니다. getHeight 메서드는 특정 노드의 깊이를 계산하기 위해 호출됩니다.

예시

아래의 이진 트리를 고려해 보겠습니다.

이진 트리에 대하여 target = 3일 때, 해당 노드의 높이는 0입니다. target = 2일 때 높이는 1입니다. target = 4일 때 높이는 2입니다. 존재하지 않는 노드에 대해서는 -1을 반환해야 하며, 예를 들어 target = 6일 때 결과는 -1입니다.

결론

이번 강좌에서는 이진 트리를 탐색하는 방법과 높이를 계산하는 방법에 대해 알아보았습니다. 이러한 트리 구조는 코딩 테스트에서 자주 등장하므로 잘 이해하고 연습해 두는 것이 중요합니다. 알고리즘을 연습할수록 각 문제를 해결하는 데 필요한 사고 과정이 생기고, 자신감을 갖게 될 것입니다.