题目:二叉排序树,统计最后两层节点个数

思路:数组格式存储,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;
}

最新文章

  1. Google翻译之路
  2. Ubuntu下git的安装与使用
  3. iOS开发 - OC - 实现本地数据存储的几种方式一
  4. C#添加dll引用后,添加命名空间出错的解决方案
  5. JBoss集群中启用HTTPS协议
  6. ylbtech-LanguageSamples-Struct(结构)
  7. hibernate tool连接oracle生成pojo和xml文件无法查询表解决办法
  8. LINUX HA:Pacemaker + Corosync初配成功
  9. Fedora安装qt总结四种方法
  10. webapi单元测试时出现的ConfigurationManager.ConnectionStrings为空错误
  11. QT+vs2010下改变可执行程序的图标
  12. uva 571 素数的性质
  13. Codeforces Round #349 (Div. 2) C. Reberland Linguistics (DP)
  14. mysql常用的函数
  15. 学号:201621123032 《Java程序设计》第10周学习总结
  16. 讲一讲MySQL如何防止“老鼠屎”类型的SQL语句
  17. &lt;spark&gt; hadoop/spark 集群搭建
  18. js-ES6学习笔记-Generator函数的应用
  19. Package gtk+-3.0 was not found in the pkg-config search path
  20. +5v to +13v Converter

热门文章

  1. bzoj 3262 陌上花开
  2. AOJ DSL_2_A Range Minimum Query (RMQ)
  3. NodeJS:Error: Cannot find module &#39;jshint/src/cli&#39;
  4. 前端模块化工具-webpack
  5. php操作mongodb
  6. PL/SQL设置主键自增
  7. Google Map API V3开发(1)
  8. python程序一直在后台运行的解决办法
  9. HTML5视频播放
  10. kindeditor在光标处插入编辑器外的数据