题意:
给一个二叉树序列,判断是不是一颗二叉搜索树
思路:
根据给的二叉树序列先把树建立出来,然后前序遍历二叉树,如果这是一颗搜索二叉树的话,那么前序遍历的
序列一定是单调不递减的,所以我们只需要判断这个序列是不是单调不递减即可,还是考察对搜索二叉树的结构的理解
代码
#include <bits/stdc++.h> using namespace std; const int maxn = 80000 + 5; const int inf = 1e9 + 7; const int mod = 1e9 + 7; const double PI = acos(-1.0); struct Node { int v,lch,rch; }node[maxn]; bool flag; vector <int> a; void forder(int rt) { if(!rt) return ; forder(node[rt].lch); a.push_back(node[rt].v); forder(node[rt].rch); } int main() { std::ios::sync_with_stdio(false); int t; cin>>t; while(t--){ memset(node,0,sizeof node); flag = true; int m,root;//节点数量和根节点标号 cin>>m>>root; for(int i = 1; i <= m; i++){ int v,l,r; cin>>v>>l>>r; node[i].v = v,node[i].lch = l,node[i].rch = r; } a.clear(); forder(root); for(int i = 0; i < a.size() - 1; i++){ if(a[i] > a[i + 1]){ flag = false; break; } } if(flag) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }