pat L2-006- 이미 알고 있는 두 갈래 나무의 뒷차례 서열과 중차례 서열 구층차례 역행 결과

2267 단어

L2-006. 나무가 두루 다니다


시간 제한
400 ms
메모리 제한 사항
65536 kB
코드 길이 제한
8000 B
판정 절차
Standard
작자
진부하다
두 갈래 나무의 뒷차례와 중간차례를 정해 주십시오. 층차례가 흐르는 순서를 출력해 주십시오.여기서 키 값이 서로 같지 않은 정수라고 가정합니다.
형식 입력:
첫 번째 줄을 입력하면 두 갈래 나무의 결점 개수인 정수 N(<=30)이 표시됩니다.두 번째 줄은 그 후의 서열을 반복한다.세 번째 줄은 그 중의 서열을 반복한다.숫자 사이는 공백으로 구분된다.
출력 형식:
한 줄에서 이 나무의 층층이 흐르는 서열을 출력합니다.숫자 사이는 1개의 공백으로 구분되며, 줄의 앞뒤에 여분의 공백이 있어서는 안 된다.
샘플 입력:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

내보내기 예제:
4 1 6 3 5 7 2

#include
#include
#include
#include
#include
#include
using namespace std;
struct Node{
int r;
int l;
};
int be[35],mid[35],N;
Node tree[35];
intbuild(intlb, intrb, intlm, intrm)/lb, rb는 뒷순서의 맨 왼쪽과 맨 오른쪽,lm,rm는 중간순서의 맨 왼쪽과 맨 오른쪽을 대표한다
{
//반복 중지 조건에 주의하십시오. 그렇지 않으면 무한 반복됩니다.
if (lb > rb)//0과 같을 때 이 루트에 하위 노드가 없음을 나타냅니다
return 0;
//뒤의 마지막 원소는 반드시 이 나무의 뿌리이다
int root = be[rb],x,y;
//루트 찾기
x = lm; 
while(mid[x] != root) x++;
y = x - lm;
//뿌리가 몇 번째 위치에 있는지 확인하고 양쪽으로 나누어 뿌리의 좌우 노드를 찾는다
tree[root].l = build(lb,lb+y-1,lm,x-1);
tree[root].r = build(lb+y,rb-1,x+1,rm); 
//특정 노드를 나타내는 숫자로 돌아가기
return root;
}
void BFS(int root)
{
queue q;
vector v;
q.push(root);
while(!q.empty())
{
int temp = q.front();
q.pop();
v.push_back(temp);
if(tree[temp].l != 0)
q.push(tree[temp].l);
if(tree[temp].r != 0)
q.push(tree[temp].r);
}
int len = v.size(); 
for(int i = 0; i < len-1; i++)
cout<
cout<}
int main()
{
scanf("%d",&N);
for(int i = 0; i < N; i++)
scanf("%d",&be[i]);
for(int i = 0; i < N; i++)
scanf("%d",&mid[i]);
build(0,N-1,0,N-1);
BFS(be[N-1]);
 return 0;
}
이 문제는 더 간단한 방법이 있습니다. 이 블로그->https://blog.csdn.net/qq_34594236/article/details/63273098

좋은 웹페이지 즐겨찾기