[C++知识库]L2-004 这是二叉搜索树吗？ (25 分)

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

首先前序遍历一定是在每个子树中的第一项是根节点，根节点下的左子树的所有值都小于根节点的值的，右子树的值都是大于等于根节点的值，所以可以利用子树的首项将后面的数据分为两块。可以利用递归的思想来进行操作，将树分为子树，然后将节点添加到后序遍历的数据中，就能够将前序遍历转换为后续遍历。

Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> pre, post;
bool isMirror;

void get_post(int root, int tail)
{
    if (root > tail) return;
    int i = root + 1, j = tail;
    if (!isMirror)

    {
        while (i <= tail && pre[root] > pre[i]) i++;
        while (j > root && pre[root] <= pre[j]) j--;
    }
    else
    {
        while (i <= tail && pre[root] <= pre[i]) i++;
        while (j > root && pre[root] > pre[j]) j--;
    }
    if (i - j != 1) return;		// i 和 j不相连说明这棵树不是二叉搜索树或者其镜像
    get_post(root + 1, j);
    get_post(i, tail);
    post.push_back(pre[root]);
}

int main()
{
    int n;
    cin >> n;
    pre.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> pre[i];
    }
    isMirror = false;
    get_post(0, n - 1);
    if (post.size() != n)
    {
        isMirror = true;
        post.clear();
        get_post(0, n - 1);
    }

    if (post.size() == n)
    {
        cout << "YES" << endl;
        for (int i = 0; i < n; i++)
        {
            cout << post[i];
            if (n - i > 1) cout << ' ';
        }
        cout << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}