首页 > 代码库 > PAT A 1115. Counting Nodes in a BST (30)【二叉排序树】
PAT A 1115. Counting Nodes in a BST (30)【二叉排序树】
1115
题目:二叉排序树,统计最后两层节点个数
思路:数组格式存储,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;}
PAT A 1115. Counting Nodes in a BST (30)【二叉排序树】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。