1115. Counting Nodes in a BST (30)

时间限制

400 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

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

思路

简单题，打印出二叉搜索树最后两层的节点数之和，格式为:"n1 + n2 = sum(n1,n2)"。

1.根据输入建立二叉搜索树
2.前序遍历二叉树，用一个数组统计每一层的节点数,levels[i]代表第i层的节点数，用一个maxlevel不断更新最大层数。
3.输出levels[maxlevel] + levels[maxlevel - 1]。

代码

#include<iostream>

#include<vector>

using namespace std;

vector<int> levels;

int maxlevel = -1;

class node

{

public:

    node(int _val):val(_val),left(nullptr),right(nullptr)

    {

    }

    int val;

    node* left;

    node* right;

};

typedef node* treenode;

void buildBST(treenode& root,int val)

{

    if(val <= root->val && !root->left)

    {

        root->left = new node(val);

        return;

    }

    if(val <= root->val && root->left)

    {

        buildBST(root->left,val);

        return;

    }

    if(val > root->val && !root->right)

    {

       root->right = new node(val);

       return;

    }

    if(val > root->val && root->right)

    {

       buildBST(root->right,val);

       return;

    }

}

void countNodes(const treenode root,int level)

{

    levels[level]++;

    if(level > maxlevel)

        maxlevel = level;

    if(!root->left && !root->right)

        return;

    if(root->left)

        countNodes(root->left,level + 1);

    if(root->right)

        countNodes(root->right,level + 1);

}

int main()

{

    int n;

    while(cin >> n)

    {

        levels.resize(n + 1);

        treenode root = new node(0);

        cin >> root->val;

        for(int i = 1;i < n;i++)

        {

            int tmp;

            cin >> tmp;

            buildBST(root,tmp);

        }

        countNodes(root,1);

        cout << levels[maxlevel] << " + " << levels[maxlevel - 1] << " = " << levels[maxlevel] + levels[maxlevel - 1] << endl;

    }

}

巴特西

PAT1115:Counting Nodes in a BST

1115. Counting Nodes in a BST (30)

最新文章

热门文章