PAT 1115. Counting Nodes in a BST (30)

Posted on Edited on In

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:

9
25 30 42 16 20 20 35 -5 28

Sample Output:

2 + 4 = 6

将输入的节点插入到二叉搜索树中，把树的每个节点加入到容器中，然后遍历容器中得每个节点，求得最后两层的节点个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <vector>

using namespace std;

struct Node {
    int level, val;
    struct Node *left, *right;
};

int h = 0;
vector<struct Node *> v;

struct Node *insert(struct Node *root, int x, int l) {
    if (root == NULL) {
        root = new struct Node();
        root->val = x;
        root->level = l;
        v.push_back(root);
        h = l > h ? l : h;
    } else if (root->val >= x) {
        root->left = insert(root->left, x, l + 1);
    } else {
        root->right = insert(root->right, x, l + 1);
    }
    return root;
}

int main() {
    int n = 0;
    scanf("%d", &n);
    struct Node *root = NULL;
    for (int i = 0; i < n; i++) {
        int x = 0;
        scanf("%d", &x);
        root = insert(root, x, 1);
    }

    int n1 = 0, n2 = 0;
    for (vector<struct Node *>::iterator i = v.begin(); i != v.end(); i++) {
        if ((*i)->level == h) n1++;
        if ((*i)->level == h - 1) n2++;
    }
    printf("%d + %d = %d", n1, n2, n1 + n2);
    return 0;
}