[트리] 4256번 - 트리

🔗 문제 링크

📝 풀이 과정

전위 순회(root → left → right)

첫 방문하는 노드가 무조건 root 노드
rootIndex + 1 : left의 root 노드
rootIndex + 왼쪽 자식노드 갯수 : right의 root 노드

중위 순회(left → root → right)

왼쪽 자식 노드와 오른쪽 자식 노드의 값과 개수를 알 수 있다.
root 노드 왼쪽에 있는 값 : left에 있는 자식 노드들
root 노드 오른쪽에 있는 값 : right에 있는 자식 노드들

전위 순회 → 각 Root 노드가 되는 값 결정
중위 순회 → 왼쪽 자식 노드, 오른쪽 자식 노드의 값과 개수 파악

왼쪽 자식 노드 갯수 = (i - start)

👩🏻‍💻 제출 코드

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

public class Main {
	
	static StringBuilder sb = new StringBuilder();
	static int[] inorder, preorder;
	static int n;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int test = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		for(int t = 0; t < test; t++) {
			n = Integer.parseInt(br.readLine());
			
			preorder = new int[n+1];
			inorder = new int[n+1];
			
			st = new StringTokenizer(br.readLine());
			for(int i = 0; i < n; i++) { // 전위 순회 저장
				preorder[i] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine());
			for(int i = 0; i < n; i++) { // 중위 순회 저장
				inorder[i] = Integer.parseInt(st.nextToken());
			}
			
			postorder(0, 0, n);
			sb.append("\n");
			
		}

		System.out.println(sb.toString());
	}
	
	public static void postorder(int rootIdx, int start, int end) {
		int root = preorder[rootIdx];
		
		for(int i = start; i < end; i++) {
			if(inorder[i] == root) {
				postorder(rootIdx + 1, start,  i); // left
				postorder(rootIdx + i - start + 1, i + 1, end); // right
				sb.append(root).append(" "); // root
				return;
				
			}
		}
		
	}
}

---

References

[백준] 알고리즘 분류(트리,JAVA)4256번, 트리
BOJ 4256 - 트리(Java)