L3-016 二叉搜索树的结构 (30 分)

题目描述：

二叉搜索树：根节点的值大于左子树的所有点的值，小于右子树的所有点的值，且左子树和右子树同样是一颗二叉搜索树

给你n个数，按顺序插入二叉搜索树

m次询问，询问节点关系

思路：

如果用线段树的方式去建树，那遇到极限数据是会爆掉的，比如一个1到100的升序序列，不仅爆longlong，空间更爆，会直接RE。但是这个题数据貌似有点水，没卡？

我这里用的是数组模拟链表

#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, a, b;
string s;
int tot;
map<int, int>id;
struct ran{
    int l, r, fa, x, h;
}tr[MAX];

void inse(int x, int newid){
    tr[newid].x = x;
    int id = 1;
    while(1){
        ++tr[newid].h;
        if(x < tr[id].x){
            if(tr[id].l != 0)id = tr[id].l;
            else {
                tr[id].l = newid;
                tr[newid].fa = id;
                break;
            }
        }
        else {
            if(tr[id].r != 0)id = tr[id].r;
            else{
                tr[id].r = newid;
                tr[newid].fa = id;
                break;
            }
        }
    }
}

void work(){
    cin >> n;
    cin >> a;id[a] = 1;tr[1].x = a;
    for(int i = 2; i <= n; ++i){
        cin >> a;id[a] = i;
        inse(a, i);
    }
    cin >> m;
    while (m--) {
        cin >> a >> s;
        if(s == "is"){
            cin >> s >> s;
            if(s == "root"){
                if(a == tr[1].x)cout << "Yes\n";
                else cout << "No\n";
            }
            else if(s == "parent"){
                cin >> s >> b;
                if(id.count(a) && id.count(b) && tr[id[b]].fa == id[a])cout << "Yes\n";
                else cout << "No\n";
            }
            else if(s == "left"){
                cin >> s >> s >> b;
                if(id.count(a) && id.count(b) && tr[id[b]].l == id[a])cout << "Yes\n";
                else cout << "No\n";
            }
            else if(s == "right"){
                cin >> s >> s >> b;
                if(id.count(a) && id.count(b) && tr[id[b]].r == id[a])cout << "Yes\n";
                else cout << "No\n";
            }
        }
        else{
            cin >> b >> s >> s;
            if(s == "siblings"){
                if(id.count(a) && id.count(b) && tr[id[a]].fa == tr[id[b]].fa && tr[id[a]].fa)
                    cout << "Yes\n";
                else cout << "No\n";
            }
            else{
                cin >> s >> s >> s;
                if(id.count(a) && id.count(b) && tr[id[a]].h == tr[id[b]].h)cout << "Yes\n";
                else cout << "No\n";
            }
        }
    }
}


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