THU2017spring 2-3 Rebuild 题解

THU2017spring 2-3 Rebuild


描述

某二叉树的n个节点已经用[1, n]内的整数进行了编号。现给定该二叉树的先序遍历序列和中序遍历序列,试输出其对应的后序遍历序列。

输入

第一行为一个整数n。

第二、三行,即已知的先序、中序遍历序列,数字之间以空格分隔。

输出

仅一行。

若所给的先序、中续遍历序列的确对应于某棵二叉树,则输出其后序遍历序列,数字之间以空格分隔。否则,输出-1。

输入样例1

5
1 2 4 5 3
4 2 5 1 3

输出样例1

4 5 2 3 1

输入样例2

4
2 3 1 4
4 2 1 3

输出样例2

-1

输入样例3

8
5 2 4 1 3 6 7 8
4 2 1 5 3 7 6 8

输出样例3

4 1 2 7 8 6 3 5

限制

1 <= n <= 500,000

输入和输出的遍历序列均为[1, n]内整数的一个排列,整数间均以空格分隔。

时间:1 sec

空间:256 MB

提示

● 注意观察特殊节点在不同遍历序列中的位置

提示(.docx)

对应输入样例1的树结构:

先序遍历序列:12453
中序遍历序列:42513
注意到根节点就是先序序列的首元素,找到根节点后,根据根节点在中序序列中的位置,可划分出左右子树。

 

代码:(一个点TLE没过,其它都OK)

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
using namespace std;
int n;
int preorder[500005],inorder[500005];
enum Status{
    OK=1,
    Node_Not_Exist=2,
    Value_Not_Equal=3
};
struct node{
    int data;
    node * left;
    node * right;
    node(){
        data=-1;
        left=NULL;
        right=NULL;
    }
};
int findpos(const int * ptr,int start,int end,int value){//[start,end]
    for(int i=start;i<=end;i++){
        if(ptr[i]==value)return i;
    }
    return -1;
}
Status MakeTree(int pre_start,int pre_end,int in_start,int in_end,node * cur){
    cur->data=preorder[pre_start];
    if(pre_start>pre_end||in_start>in_end)return Node_Not_Exist;
    if(pre_start==pre_end&&in_start==in_end){
        if(preorder[pre_start]==inorder[in_start])return OK;
        else return Value_Not_Equal;
    }
    int _root_inorder_pos=findpos(inorder,in_start,in_end,cur->data);
    if(_root_inorder_pos==-1)return Value_Not_Equal; //重要!
    node * left=new node;
    node * right=new node;
    switch(MakeTree(pre_start+1,_root_inorder_pos-in_start+pre_start,in_start,_root_inorder_pos-1,left)){
    case OK:
        cur->left=left;
        break;
    case Value_Not_Equal:
        return Value_Not_Equal;
        break;
    }
    switch(MakeTree(_root_inorder_pos-in_start+pre_start+1,pre_end,_root_inorder_pos+1,in_end,right)){
    case OK:
        cur->right=right;
        break;
    case Value_Not_Equal:
        return Value_Not_Equal;
        break;
    }
    return OK;
}
void postorder(node * root){
    if(root->left!=NULL)postorder(root->left);
    if(root->right!=NULL)postorder(root->right);
    cout<<root->data<<" ";
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>preorder[i];
    }
    for(int i=1;i<=n;i++){
        cin>>inorder[i];
    }
    node * root=new node;
    if(MakeTree(1,n,1,n,root)==OK)postorder(root);
    else cout<<"-1";
}

2021.07.17重写:

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
45
46
47
48
49
50
#include <iostream>
using namespace std;
int n;
int pre[500005], mid[500005];
bool flag;
struct node {
    int v;
    node* l, * r;
    node(int v) :v(v), l(NULL), r(NULL) {}
    node(int v, node* l, node* r) :v(v), l(l), r(r) {}
};
int findInMID(int v, int ms, int me) {
    for (int i = ms; i <= me; i++)
        if (mid[i] == v)
            return i;
    return -1;
}
node* build(int ps, int pe, int ms, int me) {
    if (ps > pe || ms > me)return NULL;
    if (ps == pe && ms == me) {
        if (pre[ps] != mid[ms])flag = true;
        return new node(pre[ps]);
    }
    int mm = findInMID(pre[ps], ms, me);
    if (mm == -1) {
        flag = true;
        return NULL;
    }
    return new node(
        pre[ps],
        build(ps + 1, ps + 1 + (mm - ms - 1), ms, mm - 1),
        build(ps + mm - ms + 1, pe, mm + 1, me)
    );
}
void postTraversal(node* root) {
    if (!root)return;
    postTraversal(root->l);
    postTraversal(root->r);
    cout << root->v << " ";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++)cin >> pre[i];
    for (int i = 0; i < n; i++)cin >> mid[i];
    node* root = build(0, n - 1, 0, n - 1);
    if (flag)cout << -1;
    else postTraversal(root);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注