Skip to content

L2-004 这是二叉搜索树吗？

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 400 ms
  • 内存限制: 64 MB

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

  • 其左子树中所有结点的键值小于该结点的键值；
  • 其右子树中所有结点的键值大于等于该结点的键值；
  • 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式

输入的第一行给出正整数 N（\le 1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例 1 

7
8 6 5 7 10 8 11

输出样例 1 

YES
5 7 6 8 11 10 8

输入样例 2 

7
8 10 11 8 6 7 5

输出样例 2 

YES
11 8 10 7 5 6 8

输入样例 3 

7
8 6 8 5 10 9 11

输出样例 3 

NO

Solution

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

#define N 1000010
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define pii pair<int, int>
int n, a[N];
struct node {
    int v, ls, rs;
    node() {}
    node(int v) : v(v) {
        ls = rs = -1;
    }
} t[N];

int cnt;
bool flag;
int root;
int DFS1(int l, int r) {
    if (!flag || l > r)
        return -1;
    int id = ++cnt;
    t[id] = node(a[l]);
    if (l == r)
        return id;
    int pos = r + 1;
    for (int i = l + 1; i <= r; ++i)
        if (a[i] >= a[l]) {
            pos = i;
            break;
        }
    for (int i = pos; i <= r; ++i)
        if (a[i] < a[l]) {
            flag = 0;
            return -1;
        }
    t[id].ls = DFS1(l + 1, pos - 1);
    t[id].rs = DFS1(pos, r);
    return id;
}

int DFS2(int l, int r) {
    if (!flag || l > r)
        return -1;
    int id = ++cnt;
    t[id] = node(a[l]);
    if (l == r)
        return id;
    int pos = r + 1;
    for (int i = l + 1; i <= r; ++i)
        if (a[i] < a[l]) {
            pos = i;
            break;
        }
    for (int i = pos; i <= r; ++i)
        if (a[i] >= a[l]) {
            flag = 0;
            return -1;
        }
    t[id].ls = DFS2(l + 1, pos - 1);
    t[id].rs = DFS2(pos, r);
    return id;
}

void out(int u) {
    if (t[u].ls != -1)
        out(t[u].ls);
    if (t[u].rs != -1)
        out(t[u].rs);
    cout << t[u].v << " \n"[u == root];
}

int main() {
    // ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    memset(t, -1, sizeof t);
    flag = 1;
    cnt = 0;
    root = DFS1(1, n);
    if (flag) {
        cout << "YES\n";
        out(root);
        return 0;
    }
    memset(t, -1, sizeof t);
    flag = 1;
    cnt = 0;
    root = DFS2(1, n);
    if (flag) {
        cout << "YES\n";
        out(root);
        return 0;
    }
    cout << "NO\n";
    return 0;
}
Last update: May 4, 2022
Back to top