AcWing 1605. 二叉搜索树最后两层结点数量
原题链接
中等
作者:
leo123456
,
2020-08-22 20:04:43
,
所有人可见
,
阅读 680
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int n;
int l[N],r[N],v[N],idx;
int cnt[N],max_depth;
void insert(int &u,int w)
{
if(!u)
{
u=++idx;
v[u]=w;
}
else if(w<=v[u]) insert(l[u],w);
else insert(r[u],w);
}
void dfs(int u,int depth)
{
cnt[depth]++;
max_depth=max(max_depth,depth);
if(l[u]) dfs(l[u],depth+1);
if(r[u]) dfs(r[u],depth+1);
// if(!u) return;
// cnt[depth]++;
// max_depth=max(max_depth,depth);
// dfs(l[u],depth+1);
// dfs(r[u],depth+1);
}
int main()
{
cin>>n;
int root=0;
for(int i=0;i<n;i++)
{
int w;
cin>>w;
insert(root,w);
}
dfs(root,0);
int c1=cnt[max_depth],c2=cnt[max_depth-1];
printf("%d + %d = %d",c1,c2,c1+c2);
return 0;
}
大佬没太看懂你的插入orz
简单粗暴的方法,动手模拟一遍就明白了.....