二叉树遍历， 给定中序遍历和后序遍历（或前序）求出任意一种其他遍历的方式。

题目：

给出后序遍历和中序遍历。 求出层序遍历

输入

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

输出

1
4 1 6 3 5 7 2

思路以及图示：

  1. 根据给出后序遍历和中序遍历，构建一个二叉树

  2. 通过bfs输出层序遍历的结点

解题代码：

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 50;
int n;
struct node{
    int data;
    node* lchild;
    node* rchild;
};
int pre[N], in[N], post[N];

node *create(int postL, int postR, int inL, int inR){
    if (postL > postR) return NULL;
    node* root = new node;
    root->data = post[postR];
    int k;
    for (k = inL; k <= inR; k++)
        if (in[k] == post[postR])
            break;
    int numLeft = k - inL;
    root->lchild = create(postL, postL + numLeft - 1, inL, k - 1);
    root->rchild = create(postL + numLeft, postR - 1, k + 1, inR);
    return root;
}
int num;
void bfs(node* root){
    queue<node*> q;
    q.push(root);
    while (!q.empty()){
        node* now = q.front();
        q.pop();
        printf("%d", now->data);
        num++;
        if (num < n) printf(" ");
        if (now->lchild != NULL) q.push(now->lchild);
        if (now->rchild != NULL) q.push(now->rchild);
    }
}
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &post[i]);
    for (int i = 0; i < n; i++) scanf("%d", &in[i]);
    node* root = create(0, n - 1, 0, n - 1);
    bfs(root);
    return 0;
}

如果是中序和前序遍历：

其他总结

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
#include <cstdio>
#include <vector>
using namespace std;
vector<int> post, in, level(100000, -1);
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++;
    level[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, cnt = 0;
    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);
    for(int i = 0; i < level.size(); i++) {
        if(level[i] != -1 && cnt != n - 1) {
            printf("%d ", level[i]);
            cnt++;
        } else if(level[i] != -1){
            printf("%d", level[i]);
            break;
        }
    }
    return 0;
}