是否同一棵二叉搜索树

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。

简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

输出格式:

对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

输入样例:

输出样例:

Yes
No
No

思路：先创建二叉搜索树，再根据先序和中序是否均相等来判断两棵树是否是同一棵树

 1 #include <cstdio> 
 2 #include <vector>
 3 #include <algorithm> 
 4 
 5 using namespace std;
 6 
 7 struct node
 8 {
 9     int data;
10     node* left;
11     node* right;
12 };
13 
14 void insert(node* &root,int x)
15 {
16     if(root==NULL)
17     {
18         root=new node;
19         root->data=x;
20         root->left=root->right=NULL;
21         return ;
22     }
23     if(x==root->data)
24         return;
25     else if(x<root->data)
26         insert(root->left,x);
27     else 
28         insert(root->right,x);
29 }
30 
31 node* Create(int data[],int n)
32 {
33     node* root=NULL;
34     for(int i=0;i<n;i++)
35     {
36         insert(root,data[i]);
37     }
38     return root;
39 }
40 
41 void preorder(node* root,vector<int> &vt)
42 {
43     if(root==NULL)
44         return;
45     vt.push_back(root->data);
46     preorder(root->left,vt);
47     preorder(root->right,vt);
48 }
49 
50 void inorder(node* root,vector<int> &vt)
51 {
52     if(root==NULL)
53         return;
54     preorder(root->left,vt);
55     vt.push_back(root->data);
56     preorder(root->right,vt);
57 }
58 
59 int main()
60 {
61     int n;
62     scanf("%d",&n);
63     while(n)
64     {
65         int L;
66         scanf("%d",&L);
67         vector<int> vt1,vt2;
68         int a[11];
69         for(int i=0;i<n;i++)
70         {
71             scanf("%d",&a[i]);
72         }
73         node* root1=Create(a,n);
74         preorder(root1,vt1);
75         inorder(root1,vt2);
76         while(L--)
77         {
78             int b[11];
79             vector<int> vt3,vt4;
80             for(int i=0;i<n;i++)
81             {
82                 scanf("%d",&b[i]);
83             }
84             node* root2=Create(b,n);
85             preorder(root2,vt3);
86             inorder(root2,vt4);
87             if(vt1==vt3&&vt2==vt4)
88                 printf("Yes\n");
89             else 
90                 printf("No\n");
91         }
92         scanf("%d",&n);
93     }
94     return 0;
95 }

是否同一棵二叉搜索树

是否同一棵二叉搜索树

输入格式:

输出格式:

输入样例:

输出样例:

相关推荐