【PAT甲级 - C++题解】1115 Counting Nodes in a Binary Search Tree

1115 Counting Nodes in a Binary Search Tree

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 [−1000,1000] 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:

n1 + n2 = n

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

Sample Input:

10
25 30 42 16 20 20 35 -5 28 22

Sample Output:

3 + 4 = 7

题意

二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

它的左、右子树也分别为二叉搜索树

将一系列数字按顺序插入到一个空的二叉搜索树中，然后，请你计算该树最低两层的结点个数并输出。输出格式如下：

n1 + n2 = n

思路

用哈希表来存储每个结点左右孩子的下标，下标对应的是 v 数组中该结点的值。

每输入一个结点就插入一次，插入函数需要注意的是第一个参数是以引用的方式传入。所以从 main 函数里调用该函数，传入的 root 会改变成 1 。并且在 insert 函数中递归调用自己，传入的第一个参数也可能会被改变。例如，一个结点的左孩子为空，我调用了 insert 函数并且第一个参数传入的是 l[u] ，那么调用了该函数后会检测出该结点的左孩子为空，会执行 u = ++idx 操作，这里的操作就等同于传入的参数 l[u] = ++idx ，因为传入的是 int& u 。

递归计算每一层结点的数量，用一个数组来存储每层结点数量，每调用一次就更新一次数组。

输出最终的结果，注意 n1 是最后一层，n2 才是倒数第二层。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int l[N], r[N], v[N], idx;
int max_depth, cnt[N];
//插入结点
void insert(int& u, int w)
{
    if (!u)
    {
        //注意u是引用传入
        //所以上个调用insert函数传入的u也会跟着改变
        u = ++idx;
        v[u] = w;
    }
    else if (v[u] >= w)    insert(l[u], w);
    else insert(r[u], w);
}
//计算每一层的结点个数
void dfs(int u, int 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\n", n1, n2, n1 + n2);
    return 0;
}