백준 2263 트리의 순회 Java [트리 순회]

https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

중위순회와 후위순회를 가지고 전위순회를 출력하면 된다!

예제가 너무 적어서 규칙을 찾기위해 조금 많은 숫자를 예제로 만들었다

      4
  2      6
1  3   5  7

중 1 2 3 4 5 6 7
후 1 3 2 5 7 6 4
전 4 2 1 3 6 5 7

 

               8
      4                   12
  2       6       10          14 
1  3   5  7   9     11  13   15

중 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
후 1 3 2 5 7 6 4 9 11 10 13 15 14 12 8
전 8 4 2 1 3 6 5 7 12 10 9 11 14 13 15

 

가장 먼저 찾은 규칙은 후위 순회 마지막이 트리의 루트 노드인 것이다

후위 순회 마지막에서 2번째가 중위순회 정점보다 왼쪽에 있으면 왼쪽노드, 오른쪽에 있으면 오른쪽노드이다

(여기서 재귀 사용해서 분할정복을 했어야했는데... 괜히 복잡하게 푼 것 같다)

 

후위순회를 스택에 담아서 하나씩 팝하고
해당 숫자가 이전에 뽑은 숫자보다 
오른쪽이면 오른쪽 자식으로 저장하고, 부모는 스택에 저장
왼쪽이면 부모 스택에서 팝해서 비교를 반복했다

 

예시 ) 

stack 8 now 8 prev
12일때
now보다 오른쪽이니까 8의 오른쪽 자식에 저장 now는 12, 부모스택에 add

stack 8 12 now 12 prev
14일때
now보다 오른쪽이니까 12의 오른쪽 자식에 저장 now는 14, 부모스택에 add

stack 8 12 14 now 14

15일때
now보다 오른쪽이니까 14의 오른쪽 자식에 저장 now는 15, 부모스택에 add

 

stack 8 12 14 15 now 15 prev
13일때 (첫번째 확인할때 no면 오른쪽에 저장)

prev = 15 now = 14 pop
now보다 왼쪽인가? yes

prev = 14 now = 12 pop
now보다 왼쪽인가? no -> prev의 왼쪽자식 저장, 12, 13 부모 스택에 add

* 리팩토링 (pop했다가 add하지말고 get으로 마지막인덱스 가져다가 비교하고 pop할지말지 정하는게 효율적일 것 같음)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static int[][] nodes;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] index = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) index[Integer.parseInt(st.nextToken())] = i;
        int[] post = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        nodes = new int[N+1][2];
        Stack<Integer> stack = new Stack<>();
        stack.add(post[N-1]);
        int now = post[N-1];
        int prev = 0;
        for(int p = N-2; p >= 0; p--) {
            if (index[post[p]] > index[now]) {
                stack.add(post[p]);
                nodes[now][1] = post[p];
                now = post[p];
                continue;
            }
            while(true) {
                if (stack.isEmpty()) {
                    nodes[now][0] = post[p];
                    now = post[p];
                    stack.add(post[p]);
                    break;
                }
                prev = now;
                now = stack.pop();
                if (index[post[p]] > index[now]) {
                    stack.add(now);
                    stack.add(post[p]);
                    nodes[prev][0] = post[p];
                    now = post[p];
                    break;
                }
            }
        }
        preorder(post[N-1]);
        System.out.println(sb);
    }
    
    static void preorder(int num) {
        Stack<Integer> stack = new Stack<>();
        stack.add(num);
        while(!stack.isEmpty()) {
            int now = stack.pop();
            sb.append(now+" ");
            if(nodes[now][1] != 0) stack.add(nodes[now][1]);
            if(nodes[now][0] != 0) stack.add(nodes[now][0]);
        }
    }
}

 

처음 돌렸을 때 한쪽으로만 길게 있는 이진트리를 고려안하고 전위순회를 재귀로 만들어서 틀렸다

그 다음엔  String에 += now + " " 이런식으로 붙였더니 메모리초과가 났다

String끼리 덧셈연산을 하면 메모리 할당과 해제를 발생시켜서 비효율적이라고 한다

String 덧셈 연산이 필요할땐 StringBuilder를 사용하자!

 

StringBuilder 참고 링크

https://www.codejava.net/java-core/the-java-language/why-use-stringbuffer-and-stringbuilder-in-java