# 题目

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

### Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤1000) which is the size of the input sequence. Then given in the next line are the N integers in [−10001000] which are supposed to be inserted into an initially empty binary search tree.

### Output Specification:

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:

where `n1` is the number of nodes in the lowest level, `n2` is that of the level above, and `n` is the sum.

# 题解

## 思路

• 建立二叉搜索树，按照给定的顺序。
• 就是从根部开始找，小的往左走，大的往右走，找到空位插进去，很直观
• 层次遍历，找到最深的两层即可。
• 不难。

## 数据结构

• Node 是一个类，包含三个属性
• 左孩子
• 右孩子
• root 是树根
• ans 存放所有的层数的出现次数。比如[1,1,3,3,4,5]代表第一层出现了2次，第3层出现了2次，第四层出现了一次。
• max_level 是最深的层数
• a,b 是最深一层的节点个数和倒数第二层的节点个数。

## 算法

• 插入算法，参数是节点和待插入的值
• 先从根节点开始
• 如果要插入的值小于等于这个节点，那么往左看
• 如果左为空，插入它
• 否则递归进入左节点，以左节点为根看能不能插入
• 如果要插入的值大于这个节点，那么往左看
• 如果右为空，插入它
• 否则递归进入右节点，以右节点为根看能不能插入
• 层次遍历。参数是节点和层级
• 先把这个层级加入到ans里
• 遍历左边的节点，层级 + 1
• 遍历右边的节点，层级 + 1

## 代码

• 这道题给的测试集并没有严格按照说好的方式来给，所以Python会有两个点非零返回。