PAT-ADVANCED1115——Counting Nodes in a BST

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805355987451904

题目描述：

题目翻译：

1115 在一棵二分搜索树中数节点数

一棵二分搜索树是一棵二叉树，递归地定义如下：

        左子树的节点都小于或等于当前节点的值。

        右子树的节点都大于当前节点的值。

        左右子树都是一棵二分搜索树。

将一系列数字插入最初为空的二分搜索树中。然后，你需要计算结果树的最低2级中的节点总数。

输入格式：

每个输入文件包含一个测试用例。对于每种情况，第一行给出正整数N(<= 1000)，它是输入序列的大小。然后在下一行给出的是[-1000, 1000]中的N个整数，它们需要被插入到最初为空的二分搜索树中。

输出格式：

对每个测试用例，在一行中打印生成树的最低2级中的节点数，格式如下：

n1 + n2 = n

其中n1是最低层的节点数，n2是第二低层的节点数，n是n1和n2的和。

输入样例：

9
25 30 42 16 20 20 35 -5 28

输出样例：

2 + 4 = 6

知识点：二分搜索树、层序遍历

思路一：按插入顺序构建二分搜索树，再层序遍历即可（静态数组实现）

时间复杂度是O(N * h)，其中h为树的深度。空间复杂度是O(N)。

C++代码：

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct node {
	int data;
	int lchild, rchild;
};

node Node[1001];
int index = 0;
vector<int> nums;
vector<int> sizes;

int newNode(int num);
void insert(int &head, int num);
int create();
void levelOrderTraversal(int head);

int main() {
	int N;
	scanf("%d", &N);
	int num;
	for(int i = 0; i < N; i++) {
		scanf("%d", &num);
		nums.push_back(num);
	}
	int head = create();
	levelOrderTraversal(head);
	int n1 = sizes[sizes.size() - 1];
	int n2 = sizes[sizes.size() - 2];
	printf("%d + %d = %d\n", n1, n2, n1 + n2);
	return 0;
}

int newNode(int num) {
	int head = index++;
	Node[head].data = num;
	Node[head].lchild = -1;
	Node[head].rchild = -1;
	return head;
}

void insert(int &head, int num) {
	if(head == -1) {
		head = newNode(num);
		return;
	}
	if(num > Node[head].data) {
		insert(Node[head].rchild, num);
	} else {
		insert(Node[head].lchild, num);
	}
}

int create() {
	int head = -1;
	for(int i = 0; i < nums.size(); i++) {
		insert(head, nums[i]);
	}
	return head;
}

void levelOrderTraversal(int head) {
	queue<int> q;
	q.push(head);
	while(!q.empty()) {
		int size = q.size();
		sizes.push_back(size);
		for(int i = 0; i < size; i++) {
			int now = q.front();
			q.pop();
			if(Node[now].lchild != -1) {
				q.push(Node[now].lchild);
			}
			if(Node[now].rchild != -1) {
				q.push(Node[now].rchild);
			}
		}
	}
}

C++解题报告：

思路二：按插入顺序构建二分搜索树，再层序遍历即可（指针实现）

时间复杂度是O(N * h)，其中h为树的深度。空间复杂度是O(N)。

C++代码：

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct node {
	int data;
	node* lchild;
	node* rchild;
};

vector<int> nums;
vector<int> sizes;

node* newNode(int num);
void insert(node* &head, int num);
node* create();
void levelOrderTraversal(node* head);

int main() {
	int N;
	scanf("%d", &N);
	int num;
	for(int i = 0; i < N; i++) {
		scanf("%d", &num);
		nums.push_back(num);
	}
	node* head = create();
	levelOrderTraversal(head);
	int n1 = sizes[sizes.size() - 1];
	int n2 = sizes[sizes.size() - 2];
	printf("%d + %d = %d\n", n1, n2, n1 + n2);
	return 0;
}

node* newNode(int num) {
	node* head = new node();
	head->data = num;
	head->lchild = NULL;
	head->rchild = NULL;
	return head;
}

void insert(node* &head, int num) {
	if(head == NULL) {
		head = newNode(num);
		return;
	}
	if(num > head->data) {
		insert(head->rchild, num);
	} else {
		insert(head->lchild, num);
	}
}

node* create() {
	node* head = NULL;
	for(int i = 0; i < nums.size(); i++) {
		insert(head, nums[i]);
	}
	return head;
}

void levelOrderTraversal(node* head) {
	queue<node*> q;
	q.push(head);
	while(!q.empty()) {
		int size = q.size();
		sizes.push_back(size);
		for(int i = 0; i < size; i++) {
			node* now = q.front();
			q.pop();
			if(now->lchild != NULL) {
				q.push(now->lchild);
			}
			if(now->rchild != NULL) {
				q.push(now->rchild);
			}
		}
	}
}

C++解题报告：