THU2017spring 2-3 Rebuild 题解

THU2017spring 2-3 Rebuild


描述

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

输入

第一行为一个整数n。

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

输出

仅一行。

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

输入样例1

1
2
3
5
1 2 4 5 3
4 2 5 1 3

输出样例1

1
4 5 2 3 1

输入样例2

1
2
3
4
2 3 1 4
4 2 1 3

输出样例2

1
-1

输入样例3

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

输出样例3

1
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";
}

发表评论

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