[Java] 트리 순회

1. 문제

트리 순회

이진 트리를 표현한 리스트 nodes 를 인자로 받습니다. 예를 들어서 nodes가 [1, 2, 3, 4, 5, 6, 7]이면 다음과 같은 트리를 표현한 것입니다. 해당 이진 트리에 대하여 전위 순회, 중위 순회, 후위 순회 결과를 반환하는 solution() 함수를 구현하세요

제약조건

• 입력 노드값의 개수는 1개 이상 1,000개 이하이다.
• 노드값은 정수형이며, 중복되지 않는다.

입출력 예

2. 접근방법

3. 정답코드

import java.util.*;

public class Solution {
    
    public static String[] solution(int[] nodes) {
        String[] result = new String[3];
        result[0] = preorder(nodes, 0).trim(); // 마지막 공백 제거
        result[1] = inorder(nodes, 0).trim();
        result[2] = postorder(nodes, 0).trim();
        return result;
    }
    
    private static String preorder(int[] nodes, int idx) {
        if (idx >= nodes.length) { // idx가 범위를 벗어나면 빈 문자열 반환
            return "";
        }
        
        // 루트 노드 → 왼쪽 서브 트리 → 오른쪽 서브 트리 → 재귀호출
        return nodes[idx] + " " + preorder(nodes, 2 * idx + 1) +
                                  preorder(nodes, 2 * idx + 2);
    }
    
    private static String inorder(int[] nodes, int idx) {
        if (idx >= nodes.length) {
            return "";
        }
        
        // 왼쪽 서브 트리 → 루트 노드 → 오른쪽 서브 트리 순으로 재귀호출
        return inorder(nodes, 2 * idx + 1) + nodes[idx] + " " +
               inorder(nodes, 2 * idx + 2);
    }
    
    private static String postorder(int[] nodes, int idx) {
        if (idx >= nodes.length) {
            return "";
        }
        
        // 왼쪽 서브 트리 → 오른쪽 서브 트리 → 루트 노드 순으로 재귀호출
        return postorder(nodes, 2 * idx + 1) + postorder(nodes, 2 * idx + 2) + nodes[idx] + " ";
    }
    
    public static void main(String args[]) {
        int[] nodes = {1, 2, 3, 4, 5, 6, 7};
        String[] result = solution(nodes);
        
        System.out.println("기존 배열: " + Arrays.toString(nodes));
        System.out.println("결과: " + Arrays.toString(result));
    }
}