摘要
Title: L2-004 这是二叉搜索树吗？ (25 分)
Tag: 二叉搜索树
Memory Limit: 64 MB
Time Limit: 1000 ms

L2-004 这是二叉搜索树吗？ (25 分)

题意

二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉搜索树
我们将二叉搜索树镜面翻转得到的树称为二叉搜索树的镜像。
现在，给定一个整数序列，请你判断它是否可能是某个二叉搜索树或其镜像进行前序遍历的结果。
思路

ps: 取消同步流后，puts不输出
对应 AcWing 1527. 判断二叉搜索树

核心思想：二叉搜索树的中序遍历是一个递增的序列，根据输入的前序遍历序列和排序之后的中序序列可以构造出一棵二叉树或者根据镜像(逆序之后的中序序列)可以构造出一棵二叉搜索树的话，则满足条件，输出后序遍历序列。

注意的点：
- 二叉搜索树这个性质，相当于给了一个中序遍历，所以根据中序遍历和前序求后序即可
- 什么时候是建不成的？
  - 就是在[il, ir]中找不到我们需要的根节点，说明这个点跑错方向了，不符合定义了
- 给的树的序列中的值不唯一？
  - 我们就不能像之前一样用哈希表将中序遍历的下标和值对应起来，只能遍历，从前往后第一个符合的
    - 为什么是从前往后第一个符合的？
    - 因为如果真的有重复的值时，如果我们选择后头的当根，那么根据左子树的定义，左边的一定小于根，但左边的还有和根相等的值，矛盾了，所以是第一个
  - 镜像同理，是从后往前第一个符合的
- 在递归中，我们先递归左子树，再右子树，后序遍历在最后输出根即可！
- build代码用来返回是否能建成符合条件的二叉搜索树，是一个递归的过程，就是遍历到当前根时，左子树、根、右子树都必须满足条件（也就是能建成）才行，然而左子树、右子树的判定值还有等它的左右子树，那么我们就可以在当前根的代码中，加入bool类型变量，承接子树递归的结果，这样各递归层就联系起来了

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-04-19 21:23:13
* @FilePath: \ACM\Acwing\1527.cpp
* @LastEditTime: 2022-04-19 21:45:45
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;

const int N = 1010;
int preorder[N], inorder[N], postorder[N];
int n, cnt;

bool build(int il, int ir, int pl, int pr, int op)
{
    if (il > ir) // 如果区间内没点了，说明这边的子树已经建完了
        return true;

    int root = preorder[pl];
    int k;
    if (op == 0)
    {
        for (k = il; k <= ir; k++)
        {
            if (inorder[k] == root)
                break;
        }
        if (k > ir)
            return false;
    }
    else
    {
        for (k = ir; k >= il; k--)
        {
            if (inorder[k] == root)
                break;
        }
        if (k < il)
            return false;
    }
    bool res = true;
    if (!build(il, k - 1, pl + 1, pl + 1 + k - 1 - il, op))
        res = false;
    if (!build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr, op))
        res = false;

    postorder[cnt++] = root;
    return res;
}

signed main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> preorder[i], inorder[i] = preorder[i];
    sort(inorder, inorder + n);
    if (build(0, n - 1, 0, n - 1, 0))
    {
        puts("YES");
        for (int i = 0; i < n; ++i)
        {
            cout << postorder[i] << " "[i == n - 1];
        }
    }
    else
    {
        reverse(inorder, inorder + n);
        cnt = 0; // 已经进行过一次build了，需要清0
        if (build(0, n - 1, 0, n - 1, 1))
        {
            puts("YES");
            for (int i = 0; i < n; ++i)
            {
                cout << postorder[i] << " "[i == n - 1];
            }
        }
        else
            puts("NO");
    }
    return 0;
}

L2-004 这是二叉搜索树吗？ (25 分)

题意

思路

代码