問題 B: 二叉搜索樹
[命題人 : 外部匯入]
時間限制 : 1.000 sec 記憶體限制 : 32 MB
題目描述
判斷兩序列是否為同一二叉搜索樹序列
輸入
開始一個數n，(1<=n<=20) 表示有n個需要判斷，n= 0 的時候輸入結束。
接下去一行是一個序列，序列長度小于10，包含(0~9)的數字，沒有重復數字，根據這個序列可以構造出一顆二叉搜索樹。
接下去的n行有n個序列，每個序列格式跟第一個序列一樣，請判斷這兩個序列是否能組成同一顆二叉搜索樹。
輸出
如果序列相同則輸出YES，否則輸出NO
樣例輸入 Copy
6
45021
12045
54120
45021
45012
21054
50412
0
樣例輸出 Copy
NO
NO
YES
NO
NO
NO
代碼：
#include <bits/stdc++.h>
using namespace std;
int A[10];
int A_size;
void shuhua(int temp)
{
A_size = 0;
do
{
A[A_size] = temp % 10;
A_size++;
temp /= 10;
} while (temp != 0);
reverse(A, A + A_size);
}
struct node
{
int data;
node* lchild;
node* rchild;
};
node* newNode(int x)
{
node* p = new node;
p->data = x;
p->lchild = p->rchild = NULL;
return p;
}
void insert(node* &root, int x)
{
if (root == NULL)
{
root = newNode(x);
return;
}
if (x <= root->data)
insert(root->lchild, x);
else if (x>root->data)
insert(root->rchild, x);
}
void creat(node* &root)
{
for (int i = 1; i < A_size; i++)
{
insert(root, A[i]);
}
}
void preorder(node* root, vector<int> &v)
{
if (root == NULL) return;
v.push_back(root->data);
preorder(root->lchild, v);
preorder(root->rchild, v);
}
void inorder(node* root, vector<int> &v)
{
if (root == NULL) return;
inorder(root->lchild, v);
v.push_back(root->data);
inorder(root->rchild, v);
}
void deleteTree(node* &root)
{
if (root == NULL) return;
deleteTree(root->lchild);
deleteTree(root->rchild);
delete root;
}
int main(void)
{
freopen("input.txt", "r", stdin);
int n, temp;
vector<int> pre1, pre2, in1, in2;
while (scanf("%d", &n) != EOF&&n != 0)
{
//root = NULL;
scanf("%d", &temp);
shuhua(temp);
node *root1 = newNode(A[0]);
creat(root1);
preorder(root1, pre1);
inorder(root1, in1);
for (int i = 0; i < n; i++)
{
pre2.clear();
in2.clear();
//root = NULL;
scanf("%d", &temp);
shuhua(temp);
node *root2 = newNode(A[0]);
creat(root2);
preorder(root2, pre2);
inorder(root2, in2);
//if (pre1 == pre2&&in1 == in2) printf("YES\n");
//else printf("NO\n");
puts(pre1 == pre2 && in1 == in2 ? "YES" : "NO");
//printf("before del\n");
//deleteTree(root2);
//printf("delete finish\n");
}
}
return 0;
}
不知道哪里出錯了。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/45982.html
標籤：新手樂園
上一篇：求大佬指點迷津