题解 | # 这是二叉搜索树吗？ #

$[二叉树]$

二叉树的递归不熟

前序遍历是：根-左-右，所以前序遍历的第一个节点一定是该子树的根节点

那么根据题意，首先先找到根节点，然后将后面的区间分成左子树与右子树两个区间（拆分的依据是根据键值与根节点键值的大小关系），例如左子树的全部键值都小于根节点键值，右子树的全部键值都大于等于根节点键值；同时有可能是二叉搜索树的“镜像”，那么就是左子树的全部键值都大于等于根节点键值，右子树的全部键值都小于根节点键值；

$type$ 分类处理普通的搜索二叉树与其“镜像”

首先找出 $mid$ ，即将 $[l,r]$ 拆分成 $[l,l]$ ， $[l+1,mid-1]$ ， $[mid+1,r]$ ，对应根左右的区间； $while$ 循环找到 $mid$ ，后续判断 $[mid+1,r]$ 是否满足都大于等于 $root$ 或者都小于 $root$

if(l > r) return true;
int root = a[l];
int mid = l + 1;
if(type){
    while(mid <= r && a[mid] < root) mid ++;
    for(int i = mid + 1; i <= r; i ++){
        if(a[i] < root) return false;
    }
}
else{
    while(mid <= r && a[mid] >= root) mid ++;
    for(int i = mid + 1; i <= r; i ++){
        if(a[i] >= root) return false;
    }
}

找到当前 $[l,r]$ 的根左右后，然后递归处理左右两个子树 $[l+1,mid-1]$ ， $[mid+1,r]$

bool ok_left = dfs(l + 1, mid - 1, ans, type);
bool ok_right = dfs(mid, r, ans, type);

当 $ok\_left$ 和 $ok\_right$ 都为 $true$ ，表示左右两个子树都满足条件，所以就将该层的根节点 $push$ 到 $ans$ 中，然后返回上一层......

所以这么递归返回，求出的 $ans$ 是后序排列
原因在于

bool ok_left = dfs(l + 1, mid - 1, ans, type);
bool ok_right = dfs(mid, r, ans, type);

if(ok_left && ok_right){
    ans.push_back(root);
    return true;
}
else return false;

是先递归了左右子树，然后才将该层的根节点 $push$ 到 $ans$ 中

如果是求中序，那么就是：

bool ok_left = dfs(l + 1, mid - 1, ans, type);
ans.push_back(root);
bool ok_right = dfs(mid, r, ans, type);

if(ok_left && ok_right) return true;
else{
    ans.pop_back();
    return false;
}

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 1100;

int n, a[N];

bool dfs(int l, int r, vector<int>& ans, bool type){
    if(l > r) return true;
    int root = a[l];
    int mid = l + 1;
    if(type){
        while(mid <= r && a[mid] < root) mid ++;
        for(int i = mid + 1; i <= r; i ++){
            if(a[i] < root) return false;
        }
    }
    else{
        while(mid <= r && a[mid] >= root) mid ++;
        for(int i = mid + 1; i <= r; i ++){
            if(a[i] >= root) return false;
        }
    }
    bool ok_left = dfs(l + 1, mid - 1, ans, type);
    bool ok_right = dfs(mid, r, ans, type);

    if(ok_left && ok_right){
        ans.push_back(root);
        return true;
    }
    else return false;
}
void solve(){

    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    vector<int> ans;
    bool ok = dfs(1, n, ans, false);
    if(!ok){
        ans.clear();
        ok = dfs(1, n, ans, true);
    }
    if(ok){
        cout << "YES" << endl;
        for(int i = 0; i < n; i ++) cout << ans[i] << (i < n - 1 ? " " : "");
    }
    else cout << "NO" ;
    return ;
}

signed main(){
    HelloWorld;
    
    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目二：树的遍历，https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805069361299456&page=1

给定一个二叉树的后序与中序，求二叉树的层序遍历的序列（层序遍历是一种按树的层级从上到下、从左到右访问所有节点的遍历方法，也称为‌广度优先遍历（BFS））

我们可以还原二叉树，然后重建边的关系，然后 $BFS$ 即可

后序是：左-右-根

中序是：左-根-右

假设 $a[]$ 是后序， $b[]$ 是中序，

所以如果现在处理一个子树区间 $[l,r]$ ，那么 $a[r]$ 就是该子树的根节点；所以我们再在 $b[]$ 里面遍历找到 $a[r]$ ，即可拆分区间

注意：在处理一个子树区间 $[l,r]$ 时，后序，中序处理的位置在原来的 $a[]$ ， $b[]$ 可能是不一样的，需要设立 $(l_{1},r_{1},l_{2},r_{2})$

（ $ma$ 和 $f\_ma$ 是用于离散化处理）

这段代码就是找到中序的根节点位置，然后拆分左右子树区间

那么此时中序的拆分为： $[l_{2},mid-1][mid,mid][mid+1,r_{2}]$

设左区间的长度 $left\_len = mid - 1 -l_{2}+1=mid-l_{2}$

所以此时后序的拆分为： $[l_{1},l_{1}+left\_len-1][l_{1}+left\_len, r_{1}-1][r_{1},r_{1}]$

int root = ma[a[r1]];
int mid = l2;
while(ma[b[mid]] != root) mid ++;

所以如果左子树区间长度 $left\_len\geq 1$ ，那么就递归左子树区间：

if(mid - l2 >= 1){
    adj[root].push_back(ma[a[l1 + left_len - 1]]);
    dfs(l1, l1 + left_len - 1, l2, mid - 1);
}

如果右子树区间长度 $r_{2}-mid\geq 1$ ，那么就递归右子树区间：

if(r2 - mid >= 1){
    adj[root].push_back(ma[a[r1 - 1]]);
    dfs(l1 + left_len, r1 - 1, mid + 1, r2);
}

最后就是基本的 $BFS$ 了

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 40;

int n, a[N], b[N];
vector<int> adj[N];
map<int, int> ma;
map<int, int> f_ma;
int idx;

void dfs(int l1, int r1, int l2, int r2){
    if(l1 > r1 || l2 > r2) return ;
    int root = ma[a[r1]];
    int mid = l2;
    while(ma[b[mid]] != root) mid ++;
    int left_len = mid - 1 - l2 + 1;
    if(mid - l2 >= 1){
        adj[root].push_back(ma[a[l1 + left_len - 1]]);
        dfs(l1, l1 + left_len - 1, l2, mid - 1);
    }
    if(r2 - mid >= 1){
        adj[root].push_back(ma[a[r1 - 1]]);
        dfs(l1 + left_len, r1 - 1, mid + 1, r2);
    }
}

void solve(){
    
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        if(!ma[a[i]]) ma[a[i]] = ++ idx, f_ma[idx] = a[i];
    }
    for(int i = 1; i <= n; i ++){
        cin >> b[i];
        if(!ma[b[i]]) ma[b[i]] = ++ idx, f_ma[idx] = b[i];
    }

    dfs(1, n, 1, n);
    queue<int> q;
    q.push(ma[a[n]]);
    vector<int> ans;
    while(q.size()){
        int u = q.front();
        q.pop();
        ans.push_back(u);
        for(int e : adj[u]) q.push(e);
    }

    for(int i = 0; i < (int)ans.size(); i ++) cout << f_ma[ans[i]] << (i < (int)ans.size() - 1 ? " " : "");
    return ;
}

signed main(){
    HelloWorld;
    
    int tt = 1; 
    while(tt --) solve();
    return 0;
}