2019Momenta校招笔试题解

交叉线
题解：

考察点： 思维，数形结合，暴力

易错点：

$1.$ 本题中要求的是相交的半圆，如果存在两个半圆，直径分别为 $[l_1,r_1]$ 和 $[l_2,r_2]$ ，并且满足 $l_1 \leq l_2，r_2 \leq r_1$ ，则不属于相交的情况，所以如果按照结束位置排序的方法来贪心并不可行

$2.$ 一定注意题目中明确说明在端点处相交不算相交

解法：

这题通过数形结合的方法更容易理解，设两个半圆的端点分别为 $[l_1,r_1]$ 和 $[l_2,r_2]$ ，则相交时有如下图所示的情况：

图片说明

在有了上述结论后，题目就变得简单，直接对于半圆 $i$ ，直接枚举其前面位置的半圆，看和其是否存在交点，复杂度为 $O(n^2)$

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e3+10;
int T,n;
int a[maxn];
struct node{
    int l,r;
}p[maxn];
int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        memset(p,0,sizeof(p));
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=2;i<=n;i++){
            p[i-1].l=min(a[i-1],a[i]);
            p[i-1].r=max(a[i-1],a[i]);
        }
        --n;
        int flag=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<i;j++){
                if((p[j].l<p[i].r&&p[j].l>p[i].l&&p[j].r>p[i].r)||(p[j].r<p[i].r&&p[j].r>p[i].l&&p[j].l<p[i].l)){
                    flag=1; 
                    break;
                }
            }
            if(flag) break;
        }
        if(!flag) printf("n\n");
        else printf("y\n");
    }
    return 0;
}

队列得分
题解：

考察点： 动态规划，分类讨论

易错点：

题目中指出 $Pi.set=P(i+1).set$ ，而 $P$ 又是取自 $S$ 队列的，因此假设当前位于 $S$ 队列当中的位置 $i$ ，则 $i$ 之前的任何位置都可能成为其在 $P$ 中的上一个位置

解法一：动态规划

设 $dp[i]$ 表示在队列 $S$ 中 $1-i$ 位置 $Score$ 的最大值， $num[i]$ 表示元素个数的最小值。根据在易错点中的分析 $i$ 之前的任意一个位置都可能成为新队列 $P$ 中位置 $i$ 的上一个位置，因此 $dp[i]$ 由所有比它小的位置和 $i$ 的作用转移过来，也即是 $dp[i]=max_{j<i}(dp[j]-(p[i].Set==p[j].Set?10:0))$ 。同时由于位于后面的位置一定不可能得到在元素更少的情况下拥有和前面位置相同的值，因此 $num[i]$ 直接由 $num[j]$ 转移过来就好了，时间复杂度为 $O(n^2)$

#include "bits/stdc++.h"
using namespace std;
const int maxn=500+10;
struct node{
    int Set,Value;
}p[maxn];
int n,dp[maxn],num[maxn];
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&p[i].Set,&p[i].Value);
    }
    int mx=0,mxnum=0;
    for(int i=1;i<=n;i++){
        int tmp=0,cur=0;
        for(int j=1;j<i;j++){
            if(tmp<dp[j]-(p[i].Set==p[j].Set?10:0)){
                tmp=dp[j]-(p[i].Set==p[j].Set?10:0);
                cur=num[j];
            }
        }
        dp[i]=tmp+p[i].Value;
        num[i]=cur+1;
        if(mx<dp[i]){
            mx=dp[i];
            mxnum=num[i];
        }
    }
    printf("%d %d\n",mx,mxnum);
    return 0;
}

解法二：分类讨论

认真分析题目，不难发现，对于选取的 $p$ 队列中连续且 $Set$ 相同元素具有如下性质：

$1.$ 如果这一段里面的所有元素都小于等于 $10$ ，则只能从中选出 $1$ 个元素，否则会起反作用，因此毫无疑问应该选取 $Value$ 值最大的那个

$2.$ 如果这一段中存在大于 $10$ 的，则只选取所有大于 $10$ 的部分，并统计个数

基于上述性质，只需分类讨论每个位置和 $10$ 的关系，同时对于连续且 $Set$ 相同的元素，看作一个 $Group$ 合在一起处理，对于 $Group$ 内的元素应用性质 $1$ 和性质 $2$ 进行分类讨论即可，时间复杂度 $O(n)$

#include "bits/stdc++.h"
using namespace std;
const int maxn=500+10;
struct node{
    int Set,Value;
}p[maxn];
int n;
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i].Set,&p[i].Value);
    int i=1;
    int sum=0,num=0;
    while(i<=n){
        int pos=i;
        int cnt=0,sum10=0,ans=0;
        while(pos<=n&&p[pos].Set==p[i].Set){
            if(p[pos].Value<=10){
                ans=max(ans,p[pos].Value);
            }
            else{
                sum10+=p[pos].Value;
                cnt++;
            }
            pos++;
        }
        if(cnt>0){
            sum+=sum10-((cnt-1)*10);
            num+=cnt;
        }else{
            sum+=ans;
            num+=1;
        }
        i=pos;
    }
    printf("%d %d\n",sum,num);
    return 0;
}

怪数
题解：

考察点： 数学，打表找规律

易错点：

注意最好把 $a$ 和 $b$ 都开成long long类型，因为在计算的过程中有可能会爆 $int$

解法：打表找规律

这题第一眼看上去并没有什么神奇的数学结论可以一眼秒掉，但数据范围又这门大，很显然可以通过打表来找规律。于是对 $100$ 以内的小数据进行暴力

#include "bits/stdc++.h"
using namespace std;
int main()
{
    for(int i=1;i<=100;i++){
        int sum=0;
        for(int j=1;j<=i;j++){
            sum+=i/j;
        }
        if(sum%2==0){
            if(i%100==0) printf("%d\n",i);
            else printf("%d ",i);
        }
    }
    printf("\n");
    return 0;
}

整理结果后有如下结果

4 5 6 7 8 
16 17 18 19 20 21 22 23 24 
36 37 38 39 40 41 42 43 44 45 46 47 48 
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 
100

很显然可以从上表中观察出来，当 $i$ 为偶数时，位于区间 $[i^2,(i+1)^2)$ 内数全为满足要求的怪数。

有了这个结论之后，对于整数 $X$ ，就可以快速统计出 $[1,X]$ 内的怪数个数。设 $v=[\sqrt{X}]$ ，则对 $v$ 进行分类讨论。如果 $v$ 是奇数，则说明从 $v^2$ 一直到 $X$ 之后不可能再存在怪数。而前面的怪数个数 $\sum_{i=0}^{i=\frac{v-1}2}4\times i+1$ 。而如果 $v$ 是偶数，则说明后面从 $v^2$ 到 $X$ 还存在怪数，故结果应该是 $\sum_{i=0}^{i=\frac{v-1}2- 1}4\times i+1$ 最后还应该加上 $X-v^2+1$ 。最后的集过应该为 $[1,b]$ 区间内的个数，减去 $[1,a-1]$ 区间内的个数。

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
LL a,b;
LL solve(LL x){
    if(x<0) return 0;
    if(x==0) return 1;
    LL v=sqrt(x),s=0;
    if(v%2){
        return v*(v+1)/2;
    }else{
        LL t=v-1;
        s=t*(t+1)/2;
        s+=x-v*v+1;
    }
    return s;
}
int main()
{
    scanf("%lld%lld",&a,&b);
    printf("%lld\n",solve(b)-solve(a-1));
    return 0;
}

大家来扫雷
题解：

考察点： 搜索

题解：

如果最开始位置 $(x,y)$ 是炸弹，则不存在可扩展的可能性，一定输出 $GG$ 。否则其他情况一定是可以扩展的。采用广度优先搜索 $(bfs)$ 进行坐标的扩展。对于一个位置 $(x,y)$ ，对其周围 $8$ 个方向进行遍历，如果有越界，或者不能扩展的位置，则剪掉；如果周围 $8$ 个方向存在数字为 $0$ 的，则将其加入队列，作为新的 $(x,y)$ 进行新一轮的扩展，直到所有的点都遇到数字边界或者地图边界。

#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> P;
const int maxn=1e3+10;
int n,m,x,y;
char s[maxn][maxn];
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};
int Count(int x,int y){
    int cnt=0;
    for(int i=0;i<8;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(s[nx][ny]=='*') cnt++;
    }
    s[x][y]=cnt+'0';
    return cnt;
}
void bfs(int x,int y){
    queue<P>que;
    que.push(make_pair(x,y));
    while(!que.empty()){
        P t=que.front();
        que.pop();
        for(int i=0;i<8;i++){
            int nx=t.first+dx[i],ny=t.second+dy[i];
            if(nx<1||nx>n||ny<1||ny>m||s[nx][ny]!='.') continue;
            int num=Count(nx,ny);
            if(num==0) que.push(make_pair(nx,ny));
        }
    }
}
int main()
{
    cin>>n>>m>>x>>y;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>s[i][j];
    if(s[x][y]=='*') cout<<"GG"<<endl;
    else{
        if(Count(x,y)==0) bfs(x,y);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) cout<<s[i][j];
            cout<<endl;
        }
    }
    return 0;
}

中位数
题解：

考察点： 思维，数形结合

解法：

题目中要求的是让 $m$ 成为新数列的中位数，则说明把新数列按照从小到大顺序排序后， $m$ 要正好处于 $[\frac {n-1}2]$ 的位置，于是采用数形结合的思想来解决此问题最为简单。首先统计原数组中小于 $m$ 的元素个数 $Small$ ，大于 $m$ 的元素个数 $Big$ ，等于 $m$ 的元素个数 $equal$ 。于是会出现有下图 $2$ 种情况：

图片说明

如左边所示，若 $Big$ 的元素个数多于 $Small$ ，为了要使得 $m$ 位于中间位置，应该使得 $Small+equal$ 变得一样长，则增加的元素应该为 $Max(Big-Small-equal,0)$ 。如右图所示，若 $Small$ 的元素多于 $Big$ ，由于 $m$ 的位置是取不超过 $\frac {n-1}2$ 的整数，于是 $Big+equal$ 的长度至少要变得比 $Small$ 大1，否则中位数位置一定位于 $Small$ 半区，所以增加元素应该为 $Max(Small-Big-equal+1,0)$ 。最后，如果 $Small$ 和 $Big$ 一样长，那如果不存在 $equal$ 则要增加 $1$ 个元素，否则 $m$ 自动位于中位数的位置上，复杂度 $O(n)$

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+100;
int n,m,a[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    int small=0,big=0,equal=0;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(a[i]<m) small++;
        else if(a[i]>m) big++;
        else equal++;
    }
    if(small<big) printf("%d\n",max(big-small-equal,0));
    else if(small>big) printf("%d\n",max(small-big-equal+1,0));
    else{
        if(equal==0) printf("1\n");
        else printf("0\n");
    }
    return 0;
}

k倍多重正整数集合
题解：

考察点： 哈希，思维

易错点：

很多同学在枚举倍数的时候会漏掉当 $k$ 的值为 $1$ 的情况，事实上，这种情况需要单独讨论， $k$ 的值为1时，集合最大可容纳的元素个数就是集合中元素的种数，也就是让集合中不同的元素只能出现1次。

题解：

这题的数据范围为 $10^5$ ，因此如果对于每个位置暴力去探寻它的 $k$ 倍是否存在与序列种显然是不可行的，因为这样复杂度为 $O(n^2)$ ， $1s$ 的时间内承受不住这么高的复杂度。可以通过空间换时间的方法来进行处理，通过哈希表来处理，这里建议选用 $map$ ， $map$ 的底层是颗红黑树，当作哈希表使用查询的复杂度是 $O(log_2n)$ 的，同时 $map$ 是有序的，可以保证枚举的时候是从小到大进行枚举的。

对于 $k$ 为 $1$ 的情况，可以直接参照易错点中所述，输出元素的类数即可。对于 $k$ 不为 $1$ 的情况，用 $map$ 统计出每个数出现的次数，然后对 $map$ 中的数从小打到进行枚举，如果当前数的 $k$ 倍在序列中，且当前数的个数不为0(因为是从小到大枚举的，很可能当前数被更小的数删除过)。则在序列中二者不能同时存在，选取二者中的出现次数更小的，将其从序列中删除，最后删完所有数，序列中余下的就是所求，复杂度 $O(nlog_2n)$

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
map<LL,int>mp;
int n;
LL k,a[maxn];
int main()
{
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        mp[a[i]]++;
    }
    if(k==1){
        printf("%d\n",mp.size());
    }else{
        for(auto &x:mp){
            if(mp.find(x.first*k)==mp.end()) continue;
            int mi=min(x.second,mp[x.first*k]);
            n-=mi;
            x.second-=mi;
            mp[x.first*k]-=mi;
        }
        printf("%d\n",n);
    }
    return 0;
}

连续子区间和
题解：

考察点： 滑动窗口，数形结合

易错点：

在本题中数据范围为 $10^6$ ，如果使用暴力求解是行不通的，因为如果使用复杂度为 $O(n^2)$ 的暴力，那运算次数将达到 $10^{12}$ ，一般来说，在 $1s$ 时间范围内 $OJ$ 所能抗住的运算次数在 $10^8-10^9$

解法：滑动窗口

首先，先从下图来观察出一个很重要的结论：

图片说明

对于一个全由正整数构成的序列来说，如果区间 $L1$ 中所有元素的和大于等于 $X$ ，则区间 $L1+L2$ 中所有元素的和一定大于等于 $X$ 。这是一个非常显然的结论，但在这里却非常有用。假设位置 $i$ 为区间 $L1$ 和 $L2$ 的分隔线， $L1$ 中所有元素的和大于等于 $X$ ，则当前位置 $i$ 对答案的贡献为 $n-i+1$ ，因为后面无论加上多少个元素，总可以，满足区间的和大于等于 $X$ 。

有了上述结论，可以很自然使用滑动窗口算法来做这个问题。对于当前位置 $i$ ，指针 $j$ 指向其所对应区间 $L1$ 的开头。如果 $XL1$ 大于 $X$ ，则指针 $j$ 从 $L1$ 的开始位置往后移动，直到 $L1$ 所对应的区间小于 $X$ 为止。同时指针每移动一次， $i$ 对答案的贡献增加 $n-i+1$ ，因为其后的都满足大于等于 $X$ 。整个过程中最多 $i$ 遍历1次， $j$ 遍历一次，所以复杂度为 $O(2n)$ ，也就是 $O(n)$ 级别的复杂度

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e6+100;
typedef long long LL;
int n,a[maxn];
LL x;
int main()
{
    scanf("%d%lld",&n,&x);
    LL sum=0,ans=0;
    int j=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
        if(sum>=x){
            ans+=n-i+1;
            while(j<=i&&sum>=x){
                sum-=a[j];
                j++;
                if(sum>=x) ans+=n-i+1;
                else break;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

交换查询
题解：

考察点： 哈希表

易错点：

因为 $n$ 和 $m$ 的范围都有 $10^5$ ，所以不能直接开成 $n \times m$ 的数组，因为这样内存会爆掉，考虑到这是 $k$ 最大也只有 $10^5$ ，说明这是一个比较稀疏的矩阵，因此可以用 $map$ 来进行存储。

解法：

定义map<pair<int,int>,int>这样一个数据结构来存储 $(x,y)$ 方格中的数字 $c$ 。定义两个数组 $x$ 和 $y$ ，分别表示行号和列号，初始化行号为 $[0,m-1]$ ，初始化列号为 $[0,n-1]$ 。每次交换 $2$ 行 $a$ 和 $b$ ，实质上相当于交换 $x[a]$ 和 $x[b]$ 中的值，相当于它们对应的行号发生变化，而每次交换 $2$ 列 $a$ 和 $b$ ，实质上相较于交换 $y[a]$ 和 $y[b]$ 中的值，相当于它们对应的列号发生变化。而对于 $query$ 操作，只需要查询 $x[a]$ 和 $y[b]$ 即可，因为在前面的交换中，已经正确完成了行号和列号的对应关系。整个算法时间复杂度为 $O(n)$

#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> P;
const int maxn=1e5+10;
int x[maxn],y[maxn];
int n,m,k,c;
map<P,int>mp;

int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<k;i++){
        P t;
        int a,b,num;
        scanf("%d%d%d",&a,&b,&num);
        t.first=a,t.second=b;
        mp[t]=num;
    }
    for(int i=1;i<n;i++) x[i]=i;
    for(int j=1;j<m;j++) y[j]=j;
    scanf("%d",&c);
    while(c--){
        int op,a,b;
        scanf("%d%d%d",&op,&a,&b);
        if(op==0){
            swap(x[a],x[b]);
        }else if(op==1){
            swap(y[a],y[b]);
        }else{
            P t;
            t.first=x[a],t.second=y[b];
            if(mp.find(t)==mp.end()) printf("-1\n");
            else printf("%d\n",mp[t]);
        }
    }
    return 0;
}

大数乘法
题解：

考察点： 模拟，字符串

易错点：

题目中明确说明了是大数的乘法，很显然会是会爆掉int或者long long类型的，所以切不可用这2种类型来记录数据，进行简单的乘法

方法一：Python

因为 $Python$ 语言支持自动高精度，因此本题如果用 $Python$ 来写就会显得尤为简单。需要注意的是 $Python$ 的输入是字符串，所以需要自己转化为对应的类型； $strip$ 去掉左右两端的空白符，返回 $str$ ； $split$ 把字符串按空白符拆开，返回 $str$ ； $map$ 把 $list$ 里面的值映射到指定类型，返回 $type$

m,n = map(int, input().split())
print(m * n)

方法二：高精度

$Python$ 语言支持自动高精度， $Java$ 语言有大数类，而C++语言中却不存在这种东西。但C++语言同样可以解决上述问题，这就需要引入一个概念，高精度。所谓高精度，就是把大整数当成字符串输入，然后通过模拟小学数学中竖式计算加减乘除的方法来计算出结果。本题中要求的高精度乘法，因此通过模拟竖式中的乘法来解决此类问题。将被乘数中的第 $i$ 位和乘数中的第 $j$ 位相乘，所得结果的个位位于 $i+j+1$ 中，所产生的进位作用于 $i+j$ 位中。基于这个思路，可以对字符串模拟写出如下代码：

#include "bits/stdc++.h"
using namespace std;
const int maxn=20000+10;
string multiply(string s1,string s2){
    if(s1=="0"||s2=="0") return "0";
    vector<int>res(s1.length()+s2.length());
    for(int i=s1.length()-1;i>=0;i--){
        int n1=s1[i]-'0';
        for(int j=s2.length()-1;j>=0;j--){
            int n2=s2[j]-'0';
            int sum=res[i+j+1]+(n1*n2);
            res[i + j + 1]=sum % 10;
            res[i + j]+=sum/10;
        }
    }
    string str="";
    for(int i=0;i<res.size();i++){
        if(i==0&&res[i]==0) continue;
        str+=res[i]+'0';
    }
    return str;
}
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    cout<<multiply(s1,s2)<<endl;
    return 0;
}

中缀表达式转后缀表达式
题解：

考察点： 栈，模拟

易错点：

由于习惯，日常生活中接触的一般为中缀表达式，导致很多同学不太明白什么是后缀表达式。后缀表达式被称为逆波兰式，是将运算符写在操作数之后的一种形式。简单来说就是如果存在E1 op E2形式的表达式，op是任意二元操作符，则E的后缀式为E1'E2' op，E1'和E2'分别为E1和E2的后缀式。有关后缀表达式的介绍可以参看百度百科

解法：栈

根据易错点中介绍的后缀表达式的知识，则有了如下思路。用一个栈来维护中缀表达式中的操作符，首先，遍历中缀表达式中的每个字符，如果是字母就直接输出，作为后缀表达式的一部分；如果是操作符，则比较其和栈顶元素的优先级，如果优先级低于栈顶元素，则将栈中元素依次出栈，直到栈为空，或者栈中元素的优先级低于当前元素，然后把该元素压栈。最后遍历完字符串之后把栈中元素全部出栈即可

#include "bits/stdc++.h"
using namespace std;
string s;
stack<char>p;
int main()
{
    cin>>s;
    unordered_map<char,int>mp;
    mp['+']=1,mp['-']=1,mp['*']=2,mp['/']=2;
    int len=s.length();
    for(int i=0;i<len;i++){
        if(s[i]>='a'&&s[i]<='z') cout<<s[i];
        else{
            while(!p.empty()&&mp[s[i]]<=mp[p.top()]){
                cout<<p.top(); p.pop();
            }
            p.push(s[i]);
        }
    }
    while(!p.empty()){
        cout<<p.top();
        p.pop();
    }
    cout<<endl;
}

最小栈
题解：

考察点： 栈

易错点：

本题要求 $min$ 、 $push$ 、 $pop$ 三种操作都在 $O(1)$ 复杂度内完成，也就是说都必须在常数时间内完成，其中 $push$ 和 $pop$ 都是栈本来的操作，很多同学会考虑使用堆来维护最小值，但是这是不对的，因为堆每次找最小值的时间复杂度为 $O(log_2n)$

题解：

可以考虑使用两个栈来共同维护，一个栈 $S$ 用来进行元素常规的出栈和入栈操作，另一个栈 $Min$ 维护最小值，其中栈顶元素表示当前栈中的最小值。对于入栈操作，首先将 $X$ 入栈 $S$ ，如果 $X$ 比 $Min$ 中的栈顶元素小，或者 $Min$ 为空，则将 $X$ 加入 $Min$ 中。对于 $min$ 操作，直接取栈 $Min$ 中的栈顶元素。对于出栈操作，栈 $S$ 直接出栈，如果当前栈顶元素等于 $Min$ 的栈顶元素，则把 $Min$ 的栈顶出栈

#include "bits/stdc++.h"
using namespace std;
stack<int>s;
stack<int>Min;
void Push(int x){
    s.push(x);
    if(Min.empty()) Min.push(x);
    else{
        int tmp=Min.top();
        if(x<=tmp) Min.push(x);
    }
}
int GetMin(){
    return Min.top();
}
int Pop(){
    int tmp=s.top(); s.pop();
    if(tmp==Min.top()&&!Min.empty()) Min.pop();
    return tmp;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int op;
        scanf("%d",&op);
        if(op==0){
            printf("%d\n",GetMin());
        }else if(op==1){
            int x; scanf("%d",&x);
            Push(x);
        }else{
            printf("%d\n",Pop());
        }
    }
    return 0;
}

二叉搜索树判定
题解：

考察点： 递归，二叉树，栈

易错点：

很多同学对于二叉搜索树的概念理解不清，二叉搜索树又被称为二叉排序树，其性质非常简单。首先二叉搜索树，可以为一颗空树，如果不是一颗空树，一定满足如下性质：若左子树非空，则左子树上所有结点均小于它的根结点；若右子树不空，则右子树上所有结点均大于它的根结点；同时，它的左右子树也分别为二叉搜索树，也就是说不仅仅是根节点满足性质，其任意一个子树同样都满足上述性质。

解法一：中序遍历(递归版)

在易错点中已经说明了二叉搜索树的性质，根据性质，如果有一种办法能先访问它的左子树，再访问它的根节点，最后访问它的右子树，这样的搜索顺序得到的序列一定满足递增的。在二叉树的所有遍历中，中序遍历恰好满足这种性质。于是可以中序遍历二叉树，看其生成的序列是否满足递增性来判断当前二叉树是否为二叉搜索树。

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<int>res;
bool flag=true;
void Inorder(TreeNode *root){
    if(root==NULL) return;
    Inorder(root->left);
    if(res.size()>0){
        int len=res.size();
        if(res[len-1]>root->val){
            flag=false;
            return;
        }
    }
    res.push_back(root->val);
    Inorder(root->right);
}
bool isBinarySearchTree(int n, TreeNode * root) {
// do something !
    Inorder(root);
    return flag
}

int main(void) 
{
    int n,r;
    scanf("%d%d",&n,&r);
    TreeNode * tree, * root;
    tree = (TreeNode*)malloc(sizeof(TreeNode)*(n+1));
    root = &tree[r];
    for (int i=1;i<=n;i++) {
    int v,l,r;
    scanf("%d%d%d",&v,&l,&r);
    tree[i].val = v;
    tree[i].left = l?&tree[l]:0;
    tree[i].right = r?&tree[r]:0;
    }
    printf(isBinarySearchTree(n,root)?"true\n":"false\n");
    return 0;
}

解法二：中序遍历(非递归版)

众所周知， $BFS$ 的本质是队列， $DFS$ 的本质是栈，所以要把递归改成非递归当让是要使用栈了。栈是一种先进后出的数据结构，先进入栈中的元素，最后从栈中出来。基于这种思想，对于每一颗子树都需要将左子树不断压栈，直到找到最左边的结点，然后再进行出栈操作，对于每一个结点的出栈，先比较和前面已出栈结点是否构成升序，然后将其指向其右指针，这样可以保证是按照中序遍历顺序出栈的。

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool isBinarySearchTree(int n, TreeNode * root) {
// do something !
    int mi=INT_MIN;
    stack<TreeNode*>s;
    while(!s.empty()||root){
        while(root){
            s.push(root);
            root=root->left;
        }
        root=s.top(); s.pop();
        if(root->val<=mi) return false;
        mi=root->val;
        root=root->right;
    }
    return true;
}

int main(void) 
{
    int n,r;
    scanf("%d%d",&n,&r);
    TreeNode * tree, * root;
    tree = (TreeNode*)malloc(sizeof(TreeNode)*(n+1));
    root = &tree[r];
    for (int i=1;i<=n;i++) {
    int v,l,r;
    scanf("%d%d%d",&v,&l,&r);
    tree[i].val = v;
    tree[i].left = l?&tree[l]:0;
    tree[i].right = r?&tree[r]:0;
    }
    printf(isBinarySearchTree(n,root)?"true\n":"false\n");
    return 0;
}