本文主要是介绍【PAT】1115. Counting Nodes in a BST (30)【树的层次遍历】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
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.
翻译：一棵二叉搜索树（BST） 按照以下规则递归定义一棵二叉树：
- 左子树的节点的键值小于等于该节点的键值。
- 右子树的节点的键值大于该节点的键值。
- 左右子树都必须也是二叉搜索树。
将一个数列插入到一棵空初始二叉搜索树中。接着你需要计算出最后得到的树的最后两层节点的个数。
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.
翻译：每个输入文件包含一组测试数据。对于每组输入数据，第一行包括一个正整数N(≤1000)，表示输入队列的长度。接下来一行包括 [−1000,1000] 的N个需要被插入空二叉搜索树的整数。
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.
翻译：对于每组输入数据，按照以下格式输出一行最后得到的树的最后两层节点之和：
n1 + n2 = n
n1表示最后一层的节点数，n2表示它的上一层的节点数，n表示它们之和。
Sample Input:
9
25 30 42 16 20 20 35 -5 28
Sample Output:
2 + 4 = 6
解题思路
将节点顺序插入二叉搜索树，然后对树进行层次遍历，用bottom和abovebottom来记录最后一层和上一层的值，详见代码。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#define INF 99999999
#define bug puts("Hello\n")
using namespace std;
int N,BST[1010][3];//0存放节点值，1存放左节点编号，2存放右节点编号
void join(int a,int root){if(BST[a][0]<=BST[root][0]){if(BST[root][1]!=0){join(a,BST[root][1]);}else BST[root][1]=a;}else{if(BST[root][2]!=0){join(a,BST[root][2]);}else BST[root][2]=a; }
}typedef pair<int,int>P;
queue<P>q;
int level[1010],bottomlevel=0,bottom=0,abovebottom=0;
void bfs(){q.push(P(0,1));while(!q.empty()){P tmp=q.front();q.pop();level[tmp.first]=tmp.second;if(bottomlevel<tmp.second){bottomlevel=tmp.second;abovebottom=bottom;bottom=1;}else if(bottomlevel==tmp.second){bottom++; }if(BST[tmp.first][1])q.push(P(BST[tmp.first][1],tmp.second+1));if(BST[tmp.first][2])q.push(P(BST[tmp.first][2],tmp.second+1));}
}int main(){scanf("%d",&N);for(int i=0;i<N;i++){scanf("%d",&BST[i][0]);if(i!=0)join(i,0);} bfs();int ans=bottom+abovebottom;printf("%d + %d = %d\n",bottom,abovebottom,ans);return 0;
}这篇关于【PAT】1115. Counting Nodes in a BST (30)【树的层次遍历】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
