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层的时候，就开始对结点计数。