浙大的这道考研上机真题的大意是给定两个序列,判定由这两个序列所构成的二叉排序树是否一样。
关键在于建树的过程和判定两棵树是否相等即可。判定两棵树是否相等可以用递归求解,先看当前结点是否相等或都为空,再看两棵子树的情况。
题目URL:http://ac.jobdu.com/problem.php?id=1009
我的AC代码,和大家分享一下。
#include<iostream>
#include<stdio.h>
using namespace std;
struct Node
{
int d;
Node *l, *r;
Node(int data)
{
d = data;
l = r = NULL;
}
};
bool search(Node * root, Node *& fa, int key)
{
if(!root) return false;
else
{
while(root)
{
fa = root;
if(key > root->d) root = root->r;
else if(key < root->d) root = root->l;
else return true;
}
return false;
}
}
void insert(Node * &root, int key)
{
if(!root)
{
root = new Node(key);
return;
}
else
{
Node *ins;
if(!search(root, ins, key))
{
if(key > ins->d) ins->r = new Node(key);
else ins->l = new Node(key);
}
}
}
bool treeCom(Node *s, Node *t)
{
if(!s && !t) return true;
else if(!s || !t) return false;
if(s->d != t->d) return false;
if(treeCom(s->l, t->l) && treeCom(s->r, t->r)) return true;
}
int main()
{
int n;
Node *r, *s;
char str[11];
while(scanf("%d", &n) && n)
{
r = NULL;
scanf("%s", str);
for(int i=0; i<10; i++) insert(r, str[i] - '0');
for(int i=0; i<n; i++)
{
s = NULL;
scanf("%s", str);
for(int i=0; i<10; i++) insert(s, str[i] - '0');
if(treeCom(r, s)) printf("YES\n");
else printf("NO\n");
}
}
system("pause");
return 0;
}