Home PAT 1119 Pre- and Post-order Traversals
Post
Cancel

PAT 1119 Pre- and Post-order Traversals

Link

已知前序、后序, 求中序.

不唯一的原因: 最后一个子树只有两个节点 A B 时, 根据前序或后序都可以推得 A 是子树的根节点, 但是 B 是 A 的左孩子还是右孩子就不得而知了.

再就是, 只需要在前序序列中找后序序列所确定的子树根节点 (postRight-1), 或者在后序序列中找前序序列所确定的子树根节点 (preLeft+1), 而不用两个都找一遍 (虽然也不会有错), 因为其中一个找出后就可以推得以 preLeft 为根节点的树的左子树的节点数量 i-preLeft-1, 然后就方便确定递归函数的参数了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
#define N 35
int n;
int pre[N],post[N];
vector<int>ans;
bool flag=true;
void build(int preLeft,int preRight,int postLeft,int postRight){
    if(preLeft>preRight||postLeft>postRight) return;
    if(preLeft==preRight){
        ans.push_back(pre[preLeft]);
        return;
    }
    if(pre[preLeft+1]==post[postRight-1]) flag=false;
    int i=preLeft+1;
    for(;i<=preRight;++i)
        if(pre[i]==post[postRight-1])
            break;
    build(preLeft+1,i-1,postLeft,postLeft+(i-preLeft-1)-1);
    ans.push_back(pre[preLeft]);
    build(i,preRight,postLeft+(i-preLeft-1),postRight-1);
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&pre[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&post[i]);
    build(1,n,1,n);
    if(flag) printf("Yes\n");
    else printf("No\n");
    for(int i=0;i<ans.size();++i){
        if(i!=0) printf(" ");
        printf("%d",ans[i]);
    }
    printf("\n");
    return 0;
}
This post is licensed under CC BY 4.0 by the author.