2020天梯赛L2-3中，如何统计二叉搜索树的第二层节点数？

本文共计650个文字，预计阅读时间需要3分钟。

二叉搜索树（BST）或空树，或具有以下性质的二叉树：若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

将一系列数字按给定顺序插入一棵初始为空的二叉搜索树，你的任务是统计结果树中最下面 2 层的结点数。

输入格式：输入在第一行给出一个正整数 N (≤1000)，为插入数字的个数。第二行给出 N 个 [−1000,1000] 区间内的整数。数字间以空格分隔。

输出格式：在一行中输出最下面 2 层的结点总数。

输入样例：

9 25 30 42 16 20 20 35 -5 28

输出样例：

6

这道题的思路就是先用递归的思想，将一个一个结点存入树当中，然后再对这棵树进行遍历，到最下面2层的时候，就开始对结点计数。

#include<bits/stdc++.h> using namespace std; int maxn=0,num=0;//maxn用来记录树的最大深度，num用来记录最下面两层的结点数 typedef struct Tnode//定义树的结构体 { int data; Tnode *lchild; Tnode *rchild; }*Bitree; void create_tree(Bitree &T,int x,int h) { if(T==NULL) { T=(Bitree)malloc(sizeof(Tnode)); T->data=x; T->lchild=NULL; T->rchild=NULL; if(maxn<h)//及时更新maxn的值 maxn=h; } else if(x<=T->data)//根据题意，小于等于根结点的值就放在左子树上 create_tree(T->lchild,x,h+1); else create_tree(T->rchild,x,h+1);//大于根结点的值就放在右子树上 } int preorder(Bitree T,int h)//先序遍历 { if(T==NULL) return 0; if(h>=maxn-1) num++;//如果已经在最下面两层，就开始对结点计数 preorder(T->lchild,h+1); preorder(T->rchild,h+1); return 1; } int main() { int n,x; Bitree T=NULL; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&x); create_tree(T,x,1); } preorder(T,1); cout<<num; return 0; }