PAT 1115. 二叉搜索树最后两层结点数量
原题链接
中等
作者:
YAX_AC
,
2024-11-27 20:55:44
,
所有人可见
,
阅读 7
//Counting Nodes in a Binary Search Tree 二叉搜索树中的节点计数
// Binary Search Tree二叉搜索树 recursively递归 properties
//subtree子树
//Insert a sequence of numbers into an initially empty binary search tree.
//他将一系列数字插入到一个最初为空的二叉搜索树中。
#include<iostream>
using namespace std;
const int N = 1010;
int n;
int l[N],r[N],v[N],idx;
int cnt[N],max_depth;
void insert(int& u,int w)
{
if(!u)
{
u = ++idx;
v[u] = w;
}
else if(w<=v[u]) insert(l[u],w);
else insert(r[u],w);
}
void dfs(int u,int depth)//depth层数
{
if(!u) return;
cnt[depth]++;
max_depth = max(max_depth,depth);
dfs(l[u],depth+1);
dfs(r[u],depth+1);
}
int main()
{
cin>>n;
int root = 0;
for(int i = 0; i<n; i++)
{
int w;
cin>>w;
insert(root,w);
}
dfs(root,0);
int n1 = cnt[max_depth],n2=cnt[max_depth-1];
printf("%d + %d = %d",n1,n2,n1+n2);
return 0;
}