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

 

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

2263번: 트리의 순회

 

 

핵심

포스트오더의 마지막 원소는 항상 루트다.

포스트오더의 왼쪽 또는 오른쪽 서브트리의 마지막 원소는
또한 인오더의 왼쪽 또는 오른쪽 서브트리의 루트다.

 

키워드

전위순회
중위순회
후위순회

 

포인트

1️⃣ 포스트오더의 마지막 원소는 루트
2️⃣ 인오더에서 해당 루트를 기준으로 좌측은 왼쪽 서브트리, 우측은 오른쪽 서브트리
3️⃣ 재귀를 이용해 서브트리를 나누고, 그 서브트리의 서브트리를 나누며 순서대로 루트를 담으면 preOrder가 된다.

 

 

//1. 포스트오더의 마지막 요소는 루트
//2. 해당루트로 인오더에서 루트의 위치를 파악
//3. 인/포스트오더의 왼쪽/오른쪽 서브트리 구하기(재귀)
//*  포스트오더 서브트리 루트는 인오더 서브트리의 루트가 되기에 
//   왼쪽/오른쪽 서브트리 범위지정 중요!

import java.util.*;
import java.io.*;

public class Main{
    static int[] inorder;
    static int[] postorder;
    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());
        inorder = new int[n + 1];
        postorder = new int[n + 1];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++) 
            inorder[i] = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++) 
            postorder[i] = Integer.parseInt(st.nextToken());
        
        getPreorder(1, n, 1, n);
        System.out.println(sb.toString().trim());
    }
    
    static void getPreorder(int inS, int inE, int postS, int postE) {
        if(inS > inE || postS > postE) return;
        
        int root = postorder[postE];
        sb.append(root).append(" ");
        
        int rootIdx = 0;
        for(int i = inS; i <= inE; i++){
            if(inorder[i] == root) {
                rootIdx = i;
                break;
            }
        }
        
        int leftTreeSize = rootIdx - inS;
        
        //포스트오더에서는 왼쪽서브트리 노드들이 오른쪽서브트리 노드들보다 먼저 나열됨.
        //그래서 포스트오더에서는 욍ㄴ쪽서브트리의 노드들을 postS부터 시작해 leftTreeSize 만큼의 노드들로 구성됨.
        //즉, 왼쪽서브트리의 마지막 노드는 postS + leftTreeSize - 1에 위치해 있다.
        getPreorder(inS, rootIdx - 1, postS, postS + leftTreeSize - 1);
        getPreorder(rootIdx + 1, inE, postS + leftTreeSize, postE - 1);
    }
}

 

 

 

기억하자 메소-드

✅  offerFirst(), offerLast() : 큐의 처음, 큐의 마지막에 원소 추가

✅  pollFirst(), pollLast() : 큐의 처음, 큐의 마지막 요소를 제거

 

✅   Map.getOrDefault(Object key, V defaultValue) 

key	찾을 키 값
defaultValue	키가 맵에 없을 경우 반환할 기본값
(예시) map.getOrDefault(c,0) + v	키 c가 맵에 없을경우 값을 0으로 설정하고 그게 아니라면 v를 더함