首页 > 代码库 > 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)【二叉排序树】