zoj 1944 Tree Recovery (데이터 구조)

1873 단어
전 서 와 중 서 구 후 서 를 알다.데이터 구 조 를 잘 배우 지 못 했 군요. 이제 업보 가 왔 습 니 다. 인공 적 으로 밀어 도 누구나 할 수 있 습 니 다. 방법 도 다 알 고 있 습 니 다. 바로 재 귀 중 순서 로 조 를 나 누 는 것 이 잖 아 요. '쓸 수 없 잖 아 요.'
망고 의 신 을 흠모 해 야 합 니까?쓰기 도 전에 그 는 지 났 다.멘 붕.
앞으로 oj 가 건설 되 었 으 니 반드시 이 문 제 를 넣 어야 한다.
이 문 제 는 나 무 를 세 울 수도 있 고 짓 지 않 을 수도 있다.
전체적인 사 고 는 dfs 에서 순서 가 있 고 전체 적 으로 앞 순 서 를 표시 하 며 앞 순서 에 따라 그룹 을 나 누 는 것 입 니 다.
트 리 버 전 만 들 기:
#include<stdio.h>
#include<string.h>
char s1[30],s2[30];
int i;
void dfs(int left,int right)
{
	int j;
	if(left>right)
		return ;
	if(left==right)//   
	{
		++i;
		printf("%c",s2[left]);
		return;
	}
	for(j=left;j<=right;++j)
	{
		if(s1[i]==s2[j])
			break;
	}
	++i;
	dfs(left,j-1);
	dfs(j+1,right);
	printf("%c",s2[j]);
}
int main()
{
	int root,l;
	while(scanf("%s%s",s1,s2)!=EOF)
	{
		l=strlen(s1);
		i=0;
		dfs(0,l-1);
		printf("
"); } return 0; }

나 무 를 세 웠 다.
#include<stdio.h>
#include<string.h>
char s1[30],s2[30];
int i;
struct node
{
	int left,right;
}a[30];
int dfs(int left,int right)
{
	int j;
	if(left>right)
		return -1;
	if(left==right)
	{
		++i;
		return s2[left]-'A';
	}
	for(j=left;j<=right;++j)
	{
		if(s1[i]==s2[j])
			break;
	}
	++i;
	a[s2[j]-'A'].left=dfs(left,j-1);
	a[s2[j]-'A'].right=dfs(j+1,right);
	return s2[j]-'A';
}
void dfs2(int x)
{
	if(a[x].left!=-1)
		dfs2(a[x].left);
	if(a[x].right!=-1)
		dfs2(a[x].right);		
	printf("%c",x+'A');
}
int main()
{
	int root,l;
	while(scanf("%s%s",s1,s2)!=EOF)
	{
		l=strlen(s1);
		for(i=0;i<26;++i)
			a[i].left=a[i].right=-1;
		i=0;
		root=dfs(0,l-1);
		dfs2(root);
		printf("
"); } }

그럼 공 앞 순 이나 공 가운데 순 이 라면?......................................................어렵다

좋은 웹페이지 즐겨찾기