알고리즘 트레이닝 순서 배열 (이차 트리 구축)

알고리즘 트레이닝 순서 배열
시간 제한: 1.0s 메모리 제한: 256.0MB
       
문제 설명
두 갈래 나무의 중순과 후순을 보여 줍니다.그것의 선순 배열을 구해내다.(약정 트리 결점은 서로 다른 대문자로 표시되며 길이는 <=8).
형식 입력
두 줄, 줄마다 문자열, 각각 중순과 후순 배열을 나타낸다
출력 형식
원하는 순서대로 배열된 문자열
　　
샘플 입력
　　BADC
　　BDCA
샘플 출력
ABCD
 
중서와 후서 배열에 대해 전서 서열을 구하는 것은 본래 나무를 세워서 실현해야 한다고 생각했는데, 결코 그런 일이 아니라 일정한 규칙을 통해 실현할 수 있다는 것을 발견하였다
먼저 뒷순서 서열에 대해 마지막은 틀림없이 맨 위의 루트 노드이다. 그러면 중순서 서열에서 루트 노드의 위치를 찾은 다음에 루트 노드의 위치에 따라 각각 왼쪽 트리와 오른쪽 트리를 훑어본다. 왼쪽 트리도 뒷순서 서열을 통해 루트 노드의 위치를 찾은 다음에 중간 순서 서열에 대응하는 위치는 왼쪽 트리와 오른쪽 트리에 대응한다.
이 문제의 한 가지 생각한 점은 후서 서열 중의 뿌리 노드에 대해 만약에 중서 서열에서 찾으면 왼쪽 나무와 오른쪽 나무의 개수를 얻어 다음 하위 나무의 안쪽으로 들어가는 뿌리 노드를 얻을 수 있다는 것이다

#include
#include
#define MAX 10

char mid[MAX],later[MAX];

void tree(int l,int r,int st,int ed)
{
	int temp=later[ed];
	if(l>r||st>ed)
	{
		return ;
	}
	else
	{
		printf("%c",temp);
		for(int i=l;i<=r;i++)
		{
			if(temp==mid[i])
			{
				tree(l,i-1,st,st+(i-1-l));
				tree(i+1,r,st+(i-l-1)+1,ed-1);
				return ;
			}
		}
	}
	return ;
}

int main()
{
	scanf("%s",mid);
	scanf("%s",later);
	int len=strlen(mid);
	tree(0,len-1,0,len-1);
	return 0;
}