HDU 1710 Binary Tree Traversals(반복)

2960 단어
Description은 두 갈래 나무의 앞 순서 반복 서열과 중간 순서 반복 서열을 제시하고 뒷 순서 반복 서열을 구한다.이후 두 줄의 n개 정수는 두 갈래 나무의 앞 순서 역행 시퀀스와 중간 순서 역행 시퀀스 Output 출력 후 순서 역행 시퀀스 Sample Input 9 1 2 4 7 7 2 8 5 9 3 6 Sample Output 7 4 2 8 9 5 6 3 1 Solution 앞 순서 역행 시퀀스의 첫 번째 요소는 루트 포인트입니다. 중간 순서 역행 시퀀스에서 루트를 찾으면 중간 순서 역행 시퀀스를 두 부분으로 나눈다. 각각 왼쪽 트리와 오른쪽 트리이다.두 부분의 길이를 알면 이 두 부분의 앞 순서를 반복해서 서열을 얻을 수 있고, 그 다음에 이 두 부분으로 돌아가면 Code
#include <stdio.h>
#include <string.h>
#define maxn 1111
int n,pre[maxn],in[maxn],post[maxn],id[maxn],res;//pre ,in  
void print(int a,int b,int c,int d)//a,b,c,d  
{
    int i=id[pre[a]];//  
    int j=i-c;//  
    int k=d-i;//  
    if(j) print(a+1,a+j,c,i-1);//  
    if(k) print(a+j+1,b,i+1,d);//  
    post[res++]=pre[a];
}
int main()
{
    while(~scanf("%d",&n))
    {
        res=0;
        for(int i=0;i<n;i++)scanf("%d",&pre[i]);
        for(int i=0;i<n;i++)scanf("%d",&in[i]),id[in[i]]=i;
        print(0,n-1,0,n-1);
        for(int i=0;i<n;i++)
            printf("%d%c",post[i],i==n-1?'
':' ');
    }
    return 0;
}
검지 Offer 문제 풀이 시리즈 - 20 두 갈래 트리 중 어느 값의 경로!!!
대칭복사 두 갈래 트리 (반복판)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage