PAT A 1115. Counting Nodes in a BST (30)【二叉排序树】
2024-09-24 19:15:35
题目:二叉排序树,统计最后两层节点个数
思路:数组格式存储,insert建树,dfs遍历
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF = 0x7FFFFFFF;
const int maxn = 1e5 + 10;
int n, cnt[maxn], a[maxn];
int ch[maxn][2], root; void insert(int &x,int y)
{
if(!x){x=y;return;}
if(a[y]<=a[x])insert(ch[x][0],y);
else insert(ch[x][1],y);
} void dfs(int x,int dep)
{
if(!x)return;
cnt[dep]++;
dfs(ch[x][0],dep+1);
dfs(ch[x][1],dep+1);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
insert(root,i);
}
dfs(root,1);
for(int i=n;i;i--)
{
if(cnt[i])
{
printf("%d + %d = %d\n",cnt[i],cnt[i-1],cnt[i]+cnt[i-1]);
break;
}
}
return 0;
}
最新文章
- Google翻译之路
- Ubuntu下git的安装与使用
- iOS开发 - OC - 实现本地数据存储的几种方式一
- C#添加dll引用后,添加命名空间出错的解决方案
- JBoss集群中启用HTTPS协议
- ylbtech-LanguageSamples-Struct(结构)
- hibernate tool连接oracle生成pojo和xml文件无法查询表解决办法
- LINUX HA:Pacemaker + Corosync初配成功
- Fedora安装qt总结四种方法
- webapi单元测试时出现的ConfigurationManager.ConnectionStrings为空错误
- QT+vs2010下改变可执行程序的图标
- uva 571 素数的性质
- Codeforces Round #349 (Div. 2) C. Reberland Linguistics (DP)
- mysql常用的函数
- 学号:201621123032 《Java程序设计》第10周学习总结
- 讲一讲MySQL如何防止“老鼠屎”类型的SQL语句
- <;spark>; hadoop/spark 集群搭建
- js-ES6学习笔记-Generator函数的应用
- Package gtk+-3.0 was not found in the pkg-config search path
- +5v to +13v Converter