문제 정의
주어진 이진 트리에서 홀수 레벨에 있는 노드들의 합과 짝수 레벨에 있는 노드들의 합의 차이를 구하는 프로그램을 작성해야 합니다.
여기서 레벨의 기준은 다음과 같습니다. 루트 노드를 1레벨로 가정하고, 루트의 왼쪽/오른쪽 자식은 2레벨, 그 아래 자식들은 3레벨로 계산합니다. 즉, 홀수 번째 깊이와 짝수 번째 깊이를 구분하여 각각의 노드 값 합계를 구한 뒤 그 차이를 반환하면 됩니다.
예시
다음과 같은 이진 트리가 주어졌다고 가정해 보겠습니다.
5
/ \
2 6
/ \ \
1 4 8
/ / \
3 7 9
각 레벨별 합계는 다음과 같이 계산됩니다.
- 홀수 레벨(1, 3레벨) 노드의 합: 5 + 1 + 4 + 8 = 18
- 짝수 레벨(2, 4레벨) 노드의 합: 2 + 6 + 3 + 7 + 9 = 27
- 차이: 18 − 27 = -9
해결 접근 방식
이 문제는 재귀적 순회(Recursive Traversal)를 활용하면 간단하게 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 트리를 순회하는 과정에서 현재 노드의 값에서 왼쪽 서브트리와 오른쪽 서브트리의 결과값을 빼서 반환하는 것입니다. 이렇게 하면 부모 노드(홀수 레벨)는 양수로 더해지고, 자식 노드(짝수 레벨)는 음수로 빼지면서 자연스럽게 레벨 간 부호가 교대로 적용됩니다. 최종적으로 루트에서 반환되는 값이 곧 홀수 레벨 합과 짝수 레벨 합의 차이가 됩니다.
알고리즘 동작 원리
- 노드가 null이면 0을 반환합니다. (재귀 종료 조건)
- 현재 노드의 데이터에서 왼쪽 자식 재귀 호출 결과와 오른쪽 자식 재귀 호출 결과를 뺍니다.
- 그 값을 상위 호출로 반환합니다.
Java 구현 코드
다음은 위 알고리즘을 Java로 구현한 전체 코드입니다.
class Node {
int data;
Node left, right;
Node(int data){
this.data = data;
this.left = this.right = null;
}
}
public class JavaTester {
public static Node getTree(){
Node root = new Node(5);
root.left = new Node(2);
root.right = new Node(6);
root.left.left = new Node(1);
root.left.right = new Node(4);
root.left.right.left = new Node(3);
root.right.right = new Node(8);
root.right.right.right = new Node(9);
root.right.right.left = new Node(7);
return root;
}
public static int difference(Node node){
if(node == null) return 0;
return node.data - difference(node.left) - difference(node.right);
}
public static void main(String args[]){
Node tree = getTree();
System.out.println(difference(tree));
}
}실행 결과
-9
복잡도 분석
- 시간 복잡도: O(n) — 트리의 모든 노드를 한 번씩 방문합니다.
- 공간 복잡도: O(h) — 재귀 호출 스택의 깊이는 트리의 높이(h)에 비례합니다. 트리가 균형 잡혀 있으면 O(log n), 편향된 경우 최악 O(n)입니다.
마무리
이처럼 재귀를 활용하면 별도의 레벨 추적 변수 없이도 부호 교대만으로 홀수/짝수 레벨의 합 차이를 우아하게 계산할 수 있습니다. 코드가 매우 간결하면서도 직관적이기 때문에 이진 트리 순회 문제의 대표적인 패턴 중 하나로 꼽힙니다.