Data Structures and Algorithms7-20——Binary Search Tree
我的Data Structures and Algorithms代码仓:https://github.com/617076674/Data-Structures-and-Algorithms原题链接:https://pintia.cn/problem-sets/16/problems/682题目描述:知识点:二分搜索树的构建、树的前序遍历思路:根据插入序列重建二分搜索树,判断树...
·
我的Data Structures and Algorithms代码仓:https://github.com/617076674/Data-Structures-and-Algorithms
原题链接:https://pintia.cn/problem-sets/16/problems/682
题目描述:
知识点:二分搜索树的构建、树的前序遍历
思路:根据插入序列重建二分搜索树,判断树的前序遍历是否相同
时间复杂度和输入数据的测试用例多少有关,对于一个测试用例,给定N和L,其时间复杂度和空间复杂度均是O(N * L)。
C++代码:
#include<iostream>
#include<vector>
using namespace std;
struct node {
int data;
node* lchild;
node* rchild;
};
int N, L;
node* newNode(int num);
void insert(node* &head, int num);
node* create(int* nums);
void preOrderTraversal(node* head, vector<int> &preOrder);
int main() {
while(true) {
scanf("%d", &N);
if(N == 0) {
break;
}
scanf("%d", &L);
int nums[N];
for(int j = 0; j < N; j++) {
scanf("%d", &nums[j]);
}
node* head = create(nums);
vector<int> preOrder;
preOrderTraversal(head, preOrder);
for(int i = 0; i < L; i++) {
int nums[N];
for(int j = 0; j < N; j++) {
scanf("%d", &nums[j]);
}
node* head = create(nums);
vector<int> tempPreOrder;
preOrderTraversal(head, tempPreOrder);
if(tempPreOrder == preOrder){
printf("Yes\n");
}else{
printf("No\n");
}
}
}
return 0;
}
node* newNode(int num) {
node* head = new node();
head->data = num;
head->lchild = head->rchild = NULL;
return head;
}
void insert(node* &head, int num) {
if(head == NULL) {
head = newNode(num);
return;
}
if(head->data < num) {
insert(head->rchild, num);
} else {
insert(head->lchild, num);
}
}
node* create(int* nums) {
node* head = NULL;
for(int i = 0; i < N; i++) {
insert(head, nums[i]);
}
return head;
}
void preOrderTraversal(node* head, vector<int> &preOrder){
if(head == NULL){
return;
}
preOrder.push_back(head->data);
preOrderTraversal(head->lchild, preOrder);
preOrderTraversal(head->rchild, preOrder);
}
C++解题报告:
更多推荐
已为社区贡献30条内容
所有评论(0)