AcWing 1605. 二叉搜索树最后两层结点数量
原题链接
中等
作者:
fei0825
,
2023-05-28 23:33:12
,
所有人可见
,
阅读 134
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int tr[N][3], idx, maxL; //tr[i][0]结点值 tr[i][1]左孩子下标 tr[i][2]右孩子下标
int lvl[N]; //每层结点数
void insert(int x){
int p = 0, k = 0;
while( tr[p][0] != INF ){
if( x<=tr[p][0] ){ //x小于等于该结点值
if( tr[p][1]==INF ){ //左孩子为空,赋下标
tr[p][1]=++idx;
p = tr[p][1];
k++;
break;
}
p=tr[p][1]; //否则向左孩子走
}
else{ //x大于该结点值
if( tr[p][2]==INF ){ //右孩子为空,赋下标
tr[p][2]=++idx;
p = tr[p][2];
k++;
break;
}
p=tr[p][2]; //否则向右孩子走
}
k++;
}
tr[p][0] = x; //当前点值设为x
lvl[k]++; //k层结点数加1
if( maxL<k ) maxL=k; //最深层高
}
int main(){
int n, x;
scanf("%d", &n);
memset(tr, 0x3f, sizeof tr);
while( n-- ){
scanf("%d", &x);
insert(x);
}
n = lvl[maxL], x = lvl[maxL-1]; //倒数一二两层
printf("%d + %d = %d", n, x, n+x);
return 0;
}