Boj 2263) 트리의 순회

문제

백준 2263

설명

Post-Order 와 InOrder 에서 얻을 수 있는 정보가 다름.

• PostOrder 에서는 무엇이 루트인지 알 수 있음
• InOrder 에서는 왼쪽, 오른쪽으로 노드가 몇개인지 알 수 있음

PostOrder 의 루트부터 재귀를 시작함.

• 현재 노드의 위치를 Post_Pivot 라고 하면
• 자식노드 L, R 의 PostOrder 내의 위치를 알아야함.
• R은 Trivial 하게 Post_Pivot - 1 임
• L은 L == Post_Pivot - SubTreeNumber(R) - 1 이 됨.

SubTreeNumber() 는 InOrder 을 통해서 얻을 수 있음

• 현재 노드의 위치인 cur_p
  • cur_p 은 아래 코드처럼 매핑으로 바로 얻을 수 있음.
• 현재 노드의 Subtree 의 시작과 끝 위치인 L_Range, R_Range
  • 편의상 포함되는 위치의 바로 다음 위치를 가르키게함.
  • L_Range , R_Range 는 재귀적으로 업데이트 됨.
    • 초기값은 트리 전체의 시작과 끝, 즉 -1, n 이 됨.
    • 다음 재귀에서는 왼쪽 Subtree 에선 L_Range, cur_p
    • 오른쪽 Subtree 에선 cur_p, R_Range
• SubTreeNumber(R) 은 R_Range - cur_p + 1 임이 자명함.
  • 그래서 L == Post_Pivot - (R_Range - cur_p) 가 되는 것

시간복잡도

O(\(N\))

코드

int in_or[100001];
int post_or[100001];

void DFS(int l_range, int r_range, int post_pivot)
{
	int cur_node, cur_p;

	cur_node = post_or[post_pivot];
	cur_p = in_or[cur_node];
	if (cur_p >= r_range || cur_p <= l_range) return;
	
	printf("%d ", cur_node);
	DFS(l_range, cur_p, post_pivot - (r_range - cur_p));
	DFS(cur_p, r_range, post_pivot - 1);
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int tmp;
		cin >> tmp;
		in_or[tmp] = i;
	}
	for (int i = 0; i < n; i++)
		cin >> post_or[i];

	DFS(-1, n, n - 1);
}