总结二叉树遍历相关题目，对这些基础题型总结经验。

​

1020 Tree Traversals

题目链接：1020 Tree Traversals （25 分)

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

Sample Input:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output:
4 1 6 3 5 7 2

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
#include <bits/stdc++.h>
using namespace std;

struct node {
    int index, value;
};
bool cmp(node a, node b) {
    return a.index < b.index;
}
vector<int> post, in;
vector<node> ans;
void pre(int root, int start, int end, int index) {
    if (start > end) return;
    int i = start;
    while (i < end && in[i] != post[root]) i++;
    ans.push_back({index, post[root]});
    pre(root - 1 - end + i, start, i - 1, 2 * index + 1);
    pre(root - 1, i + 1, end, 2 * index + 2);
}
int main() {
    int n;
    scanf("%d", &n);
    post.resize(n);
    in.resize(n);
    for (int i = 0; i < n; i++) scanf("%d", &post[i]);
    for (int i = 0; i < n; i++) scanf("%d", &in[i]);
    pre(n - 1, 0, n - 1, 0);
    sort(ans.begin(), ans.end(), cmp);
    for (int i = 0; i < ans.size(); i++) {
        if (i != 0) cout << " ";
        cout << ans[i].value;
    }
    return 0;
}

​

1138 Postorder Traversal

题目链接：1138 Postorder Traversal

给定先序和中序，求后序第一个数字

Sample Input:
7
1 2 3 4 5 6 7
2 3 1 5 4 7 6
Sample Output:
3

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

#include <bits/stdc++.h>
#define For(i, m, n) for (int i = m; i < n; i++)
using namespace std;

vector<int> pre, in;
bool flag;

void post(int root, int start, int end){
    if(start > end || flag) return;
    int i = start;
    while(in[i]!=pre[root]) i++;
    post(root+1, start, i - 1);
    post(root+i-start+1, i + 1, end);
    //printf("%d ", in[i]);
    if(!flag){
        printf("%d", in[i]);
        flag = true;
    }
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        flag = false; //用于判断是否已经找到第一个数字
        pre.resize(n);
        in.resize(n);
        For(i, 0, n) scanf("%d", &pre[i]);
        For(i, 0, n) scanf("%d", &in[i]);
        post(0, 0, n - 1);
    }
    return 0;
}

​

1119 Pre- and Post-order Traversals

题目链接：1119 Pre- and Post-order Traversals （30 分)

给出一棵树的结点个数 n，以及它的前序遍历和后序遍历，输出它的中序遍历，如果中序遍历不唯一就输出No，且输出其中一个中序即可，如果中序遍历唯一就输出Yes，并输出它的中序。

Sample Input 1:
7
1 2 3 4 6 7 5
2 6 7 4 5 3 1
Sample Output 1:
Yes
2 1 6 4 7 3 5
Sample Input 2:
4
1 2 3 4
2 4 3 1
Sample Output 2:
No
2 1 3 4

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

#include <bits/stdc++.h>
using namespace std;

vector<int> in, pre, post;
bool uniq = true;
void getIn(int preLeft, int preRight, int postLeft, int postRight) {
    if(preLeft == preRight) {
        in.push_back(pre[preLeft]);
        return;
    }
    if (pre[preLeft] == post[postRight]) {
        int i = preLeft + 1;
        while (i <= preRight && pre[i] != post[postRight-1]) i++;
        if (i - preLeft > 1)
            getIn(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) - 1);
        else
            uniq = false;
        in.push_back(post[postRight]);
        getIn(i, preRight, postLeft + (i - preLeft - 1), postRight - 1);
    }
}
int main() {
    int n;
    scanf("%d", &n);
    pre.resize(n), post.resize(n);
    for (int i = 0; i < n; i++) scanf("%d", &pre[i]);
    for (int i = 0; i < n; i++) scanf("%d", &post[i]);
    getIn(0, n-1, 0, n-1);
    printf("%s\n%d", uniq == true ? "Yes" : "No", in[0]);
    for (int i = 1; i < in.size(); i++)
        printf(" %d", in[i]);
    printf("\n");
    return 0;
}