526互联

团体天梯练习 L2-006 树的遍历

发布时间 2023-04-17 01:31:43作者: Amαdeus

L2-006 树的遍历

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

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

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

输出样例：

4 1 6 3 5 7 2

解题思路

比较考验数据结构基础的题，涉及到了根据二叉树的中序遍历和后序遍历构建二叉树，还有层序遍历。还是比较简单的，leetcode上有类似的题，我自己之前写过相关的随笔。根据前中后序遍历中的两种构造二叉树

/*   一切都是命运石之门的选择  El Psy Kongroo  */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, pii> psi;
typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
//int dx[4] = {1, -1, 0, 0};
//int dy[4] = {0, 0, 1, -1};
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;


vector<int> post;   //后序遍历序列
vector<int> res;
int n;
const int N = 33;
map<int, int> inpos;    //中序遍历对应节点值的下标
typedef struct Node{
    int val;
    struct Node *left, *right;
}Node;

//根据中序遍历和后序遍历构建二叉树
Node* build(int in_left, int in_right, int po_left, int po_right){
    if(in_left > in_right || po_left > po_right) return NULL;
    int val = post[po_right];   //后序遍历最右边的为根节点
    int in_mid = inpos[val];    //在中序遍历中找到该节点下标
    int num = in_mid - in_left; //左子树节点个数
    
    Node* root = new Node;
    root->val = val;
    root->left = build(in_left, in_mid - 1, po_left, po_left + num - 1);  
    root->right = build(in_mid + 1, in_right, po_left + num, po_right - 1);
    return root;
}

//层序遍历
void bfs(Node* root){
    queue<Node*> q;
    q.push(root);
    while(!q.empty()){
        int n = q.size();
        for(int i = 0; i < n; i ++ ){
            Node* t = q.front();
            res.push_back(t->val);
            q.pop();
            
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
    }
}

void show(){
    for(int i = 0; i < (int)res.size() - 1; i ++ ) cout << res[i] << ' ';
    cout << res.back() << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i ++ ){
        int x; cin >> x;
        post.push_back(x);
    }
    for(int i = 0; i < n; i ++ ){
        int x; cin >> x;
        inpos[x] = i;    //只需要记录中序遍历每个值对应下标就可以了
    }
    
    Node *root = build(0, n - 1, 0, n - 1);
    
    bfs(root);

    show();

    return 0;
}