TRAVELSAL RTE에러 질문있습니다!

  • BadCandy
    BadCandy

    전위 순회에서 맨 앞에있는 원소가 root이기 때문에

    root = preorder[0]을 구한 후

    중위순회에서 이 root를 기준으로 왼쪽 서브트리, 오른쪽 서브트리의 원소의 개수를 구한 후

    전위 순회, 중위 순회에서 위에서 구한 원소의 개수를 이용해서 재귀적으로 후위 순회를 출력하는 코드입니다.

    100
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

    위 처럼 트리의 원소 개수가 100개인 100개의 테스트 케이스를 만들어서 넣어보았는데도 문제가 없었습니다.

    자꾸 RTE(non zero return code)가 뜨는데.. 제가 놓친 부분이 있는지요.. 흠..

    import java.util.Arrays;
    import java.util.Scanner;

    public class Main {

    private static int N;
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
    
        int C = sc.nextInt();
    
        for (int i = 0; i < C; i++) {
    
            int N = sc.nextInt();
    
            int[] preorder = new int[N];
            int[] inorder = new int[N];
    
            for (int j = 0; j < N; j++) {
                preorder[j] = sc.nextInt();
            }
    
            for (int j = 0; j < N; j++) {
                inorder[j] = sc.nextInt();
            }
            printPostOrder(preorder, inorder);
            System.out.println();
        }
    
    }
    
    private static int[] slice(int[] array, int begin, int end) {
    
        int length = end - begin + 1;
        int[] sliceArray = new int[length];
    
        System.arraycopy(array, begin, sliceArray, 0, length);
    
        return sliceArray;
    }
    
    private static void printPostOrder(int[] preorder, int[] inorder) {
    
        int N = preorder.length;
    
        if (N == 0) return;
    
        int root = preorder[0];
    
        int L = Arrays.binarySearch(inorder, root);     // 3    (왼쪽 서브트리의 길이)
    
        printPostOrder(slice(preorder, 1, L), slice(inorder, 0, L-1));
        printPostOrder(slice(preorder, L+1, N-1), slice(inorder, L+1, N-1));
        System.out.print(root + " ");
    }

    }


    2년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    이 문제에서의 이진트리는 이진 검색 트리가 아니기 때문에, 원소들이 크기 순으로 정렬되어 있지 않습니다. 예제 데이터와 그림에서 혼란을 드려 죄송합니다. 혼란이 없도록 예제 데이터를 추가하도록 하겠습니다.


    2년 전 link
  • BadCandy
    BadCandy

    아아 그러면 이진탐색을 사용하면 안되겠군요! 감사합니다.


    2년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.