L2-011 玩转二叉树

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：

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

输出格式：

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

输入样例：

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

输出样例：

4 6 1 7 5 3 2

解题思路

首先需要根据所给的二叉树中序遍历序列和后序遍历序列得到二叉树，在这里不过多解释是怎么做的，详情可以看我之前写的另一篇随笔 根据前中后序遍历中的两种构造二叉树

然后是二叉树的镜像，这里只需要用一个递归来实现就行了。首先深度优先搜索得到镜像的左子树和镜像的右子树，然后再分别赋值给当前节点的右孩子和左孩子，最后返回当前节点。递归的边界条件也很简单，当出现空节点时，返回 \(NULL\) 即可。

最后是二叉树的层序遍历，这个也是非常基础的操作，不多说了。 二叉树的层次遍历

/*   一切都是命运石之门的选择  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, int> 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;

int n;
unordered_map<int, int> in_idx;  //中序遍历的对应下标
vector<int> pre;  //中序 前序
typedef struct node{
    int val;
    struct node *left, *right;
}node;
node *T;
vector<int> res;  //层序遍历结果

// 中序遍历和前序遍历构造二叉树
node* build(int in_l, int in_r, int pre_l, int pre_r){
    if(in_l > in_r || pre_l > pre_r) return NULL;
    int root_val = pre[pre_l];   //前序遍历第一个节点为子树根节点
    int mid = in_idx[root_val];  //定位根节点坐标
    int left_num = mid - in_l;  //左子树节点个数

    node *root = new node;
    root->val = root_val;
    root->left = build(in_l, mid - 1, pre_l + 1, pre_l + left_num);
    root->right = build(mid + 1, in_r, pre_l + left_num + 1, pre_r);

    return root;
}

//二叉树镜像
node* dfs(node *root){
    if(!root) return NULL;

    node *l = dfs(root->left);   //递归镜像左子树
    node *r = dfs(root->right);  //递归镜像右子树
    root->left = r, root->right = l;

    return root;
}

//层序遍历
void bfs(){
    queue<node*> q;
    q.push(T);

    while(!q.empty()){
        int nn = (int)q.size();
        while(nn -- ){
            node *t = q.front();
            q.pop();
            res.push_back(t->val);

            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
    }
}

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;
    pre.resize(n);
    for(int i = 0; i < n; i ++ ){
        int x; cin >> x;
        in_idx[x] = i;        //记录中序遍历各节点值对应的下标
    }
    for(int i = 0; i < n; i ++ ) cin >> pre[i];

    T = build(0, n - 1, 0, n - 1);  //建树

    T = dfs(T);     //二叉树翻转(镜像)

    bfs();

    show();

    return 0;
}