L2-3 浪漫侧影 (25 分)

题目描述：

规定一个二叉树的左视图为，同一深度的最左边的点，按深度递增输出，同样的，右视图为，同一深度的最右边的点，按深度递增输出

给定一个二叉树的中序遍历和后序遍历，问左视图、右视图

思路：

我们根据中序和后序遍历的条件来建出前序遍历的树，然后在前序遍历的基础上按深度存下所有的点，每个深度的第一个点就是左视图需要的，同样的，每个深度的最后一个点就是右视图需要的

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

int zhong[100];
int hou[100];
int pos[MAX];
int h;
vector<int>he[MAX];
void dfs(int zl, int zr, int hl, int hr, int height){
    if(zl > zr || hl > hr)return;
    int root = hou[hr];
    he[height].push_back(root);
    h = max(h, height);
    if(zl == zr || hl == hr)return;
    int mid = pos[root];
    int len1 = mid - zl;
    dfs(zl, mid - 1, hl, hl + len1 - 1, height + 1);
    dfs(mid + 1, zr, hl + len1, hr - 1, height + 1);
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> zhong[i];
        pos[zhong[i]] = i;
    }
    for(int i = 1; i <= n; ++i)cin >> hou[i];
    dfs(1, n, 1, n, 1);
    cout << "R:";
    for(int i = 1; i <= h; ++i){
        cout << ' ' << he[i].back();
    }
    cout << endl;
    cout << "L:";
    for(int i = 1; i <= h; ++i){
        cout << ' ' << he[i].front();
    }
    
}

int main(){
    io;
    work();
    return 0;
}