자바(Java)로 이진 트리의 홀수·짝수 위치 노드 합 차이 구하기

문제 개요

이진 트리가 주어졌을 때, 홀수 위치에 있는 노드들의 합과 짝수 위치에 있는 노드들의 합의 차이를 구하는 프로그램을 작성하는 것이 목표입니다.

여기서 말하는 '위치'는 레벨 순서(Level Order) 탐색을 기준으로 합니다. 각 레벨에서 왼쪽부터 차례대로 노드를 살펴보며, 해당 레벨에서 가장 먼저 만나는 노드를 홀수 위치로 간주하고 그다음 노드부터는 짝수 → 홀수 → 짝수 순으로 번갈아 분류합니다. 즉, 루트 노드는 항상 홀수 위치에서 시작합니다.

예시로 이해하기

      5
     / \
    2   6
   / \   \
  1  4    8
    /     / \
   3     7   9

위 트리를 레벨별로 나누어 계산하면 다음과 같습니다.

홀수 위치 노드의 합: 5 + 2 + (1 + 8) + (3 + 9) = 5 + 2 + 9 + 12 = 28
짝수 위치 노드의 합: 0 + 6 + 4 + 7 = 17
차이: 28 − 17 = 11

해결 접근 방법

이 문제는 레벨 순서 탐색(Level Order Traversal, BFS)을 활용하면 깔끔하게 해결할 수 있습니다.

큐(Queue)에 루트 노드를 넣고 탐색을 시작합니다.
현재 레벨에 있는 노드 수만큼 반복하면서, 레벨의 첫 번째 노드를 홀수 위치로 표시합니다.
노드를 하나 처리할 때마다 홀수/짝수 플래그를 반전시켜 다음 노드를 반대쪽 합계에 더합니다.
처리한 노드의 자식 노드들을 큐에 추가하고, 모든 노드를 처리할 때까지 위 과정을 반복합니다.
마지막에 홀수 위치 합에서 짝수 위치 합을 빼면 원하는 차이 값을 얻을 수 있습니다.

자바 구현 코드

다음은 위 알고리즘을 자바로 구현한 전체 코드입니다.

import java.util.LinkedList;

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(LinkedList<Node> queue){
        if(queue.isEmpty()) return 0;
        int evenSum = 0;
        int oddSum = 0;

        while(true){
            int nodes = queue.size();
            if(nodes == 0) break;
            boolean isOdd = true;
            while(nodes > 0){
                Node node = queue.peek();
                if(isOdd) oddSum += node.data;
                else evenSum += node.data;
                queue.remove();
                nodes--;
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
                isOdd = !isOdd;
            }
        }
        return oddSum - evenSum;
    }

    public static void main(String args[]){
        Node tree = getTree();
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(tree);
        System.out.println(difference(queue));
    }
}

코드 동작 원리