1115 Counting Nodes in a BST (30 分)【难度: 一般 / 知识点: 构建二叉搜索树】
2023-09-11 14:15:52 时间
https://pintia.cn/problem-sets/994805342720868352/problems/994805355987451904
很经典的构建搜索二叉树。
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int l[N],r[N],w[N],idx,n,x;
int cnt[N],maxv;
void insert(int &u,int c)//注意一定要引用。
{
if(!u)//无结点
{
u=++idx;//构建结点
w[u]=c;
}else if(w[u]>=c) insert(l[u],c);//左边插入
else insert(r[u],c);//右边插入
}
void dfs(int u,int deep)
{
cnt[deep]++;
maxv=max(maxv,deep);
if(l[u]) dfs(l[u],deep+1);
if(r[u]) dfs(r[u],deep+1);
}
int main(void)
{
int root=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x;
insert(root,x);
}
dfs(root,0);
printf("%d + %d = %d\n",cnt[maxv],cnt[maxv-1],cnt[maxv]+cnt[maxv-1]);
return 0;
}
相关文章
- hdu1501 记忆化搜索
- 面试官问你斐波那契数列的时候不要高兴得太早 搞懂C语言函数指针 搜索引擎还可以这么玩? 那些相见恨晚的搜索技巧
- (转)搜索引擎竟然有这么多用法:22种高级搜索语法
- 【Leetcode】98. 验证二叉搜索树(中等)
- 1043 Is It a Binary Search Tree (25 分)【难度: 中 / 知识点: 构造二叉搜索树(BST) 】
- Googler:现在可以 Linux 终端下进行 Google 搜索了!
- 如何通过Dreamweaver批量对整个站点或目录进行代码搜索或部分全部替换
- Elasticsearch 存储,搜索和分析
- 求构建不同的二叉搜索树-Python
- 修改模块搜索路径(注意:py运行完毕,就会失效,他只是临时产生效果)
- git所有分支和提交搜索
- 浅谈迭代加深搜索
- Facebook照片搜索技术揭秘
- 剑指 Offer 54. 二叉搜索树的第k大节点
- 《剑指offer》17:二叉搜索树的后序遍历
- Linux学习笔记(8)文件搜索与帮助(find)
- Apache Lucene(全文检索引擎)—搜索
- [LeetCode] 1008. Construct Binary Search Tree from Preorder Traversal 从先序遍历重建二叉搜索树
- [CareerCup] 18.8 Search String 搜索字符串
- LeetCode将有序数组转换为二叉搜索树
- 经典二分法查找的进阶题目——LeetCode33 搜索旋转排序数组