題目描述

對(duì)應(yīng)給定的一個(gè)序列可以唯一確定一棵二叉排序樹。然而，一棵給定的二叉排序樹卻可以由多種不同的序列得到。例如分別按照序列{3,1,4}和{3,4,1}插入初始為空的二叉排序樹，都得到一樣的結(jié)果。你的任務(wù)書對(duì)于輸入的各種序列，判斷它們是否能生成一樣的二叉排序樹。

輸入描述

輸入包含若干組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)的第1行給出兩個(gè)正整數(shù)N（n≤10）和L，分別是輸入序列的元素個(gè)數(shù)和需要比較的序列個(gè)數(shù)。第2行給出N個(gè)以空格分隔的正整數(shù)，作為初始插入序列生成一顆二叉排序樹。隨后L行，每行給出N個(gè)元素，屬于L個(gè)需要檢查的序列。
簡(jiǎn)單起見，我們保證每個(gè)插入序列都是1到N的一個(gè)排列。當(dāng)讀到N為0時(shí)，標(biāo)志輸入結(jié)束，這組數(shù)據(jù)不要處理。

輸出描述

對(duì)每一組需要檢查的序列，如果其生成的二叉排序樹跟初始序列生成的二叉排序樹一樣，則輸出"Yes"，否則輸出"No"。

樣例

輸入
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
輸出
Yes
No
No

思路：因?yàn)槎媾判驑涞闹行虮闅v都為一個(gè)升序序列，即中序遍歷序列都相同，又因?yàn)橐豢脴淇捎芍行虮闅v和前序遍歷所確定，因此我們判斷其前序遍歷序列是否相同即可，若前序遍歷序列相同，則樹形相同。

建樹過程：

• 先申請(qǐng)一個(gè)樹根并初始化：
  Node *rx=new Node;
  rx = NULL;
• 遞歸建樹，若遇到空結(jié)點(diǎn)，則申請(qǐng)一個(gè)新節(jié)點(diǎn)，并對(duì)其屬性初始化：
  root = new Node;
  root->id = val;

Code:

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10;
struct Node {Node* left=NULL;Node* right=NULL;int id;
};
vector<int> p,q;
map<vector<int>,bool> mp;
Node* build(Node *root,int val) {if(root == NULL) {root = new Node;root->id = val;} else if(val>=root->id) root->right = build(root->right,val);else root->left = build(root->left,val);return root;
}
void work1(Node *root) {if(root == NULL) return;p.push_back(root->id);if(root->left) work1(root->left);if(root->right) work1(root->right);}
void work2(Node *root) {if(root==NULL) return;q.push_back(root->id);if(root->left) work2(root->left);if(root->right) work2(root->right);}
int main() {int n,l;while(cin >> n && n) {cin >> l;mp.clear();Node *rx=new Node;rx = NULL;int k;for(int i=0; i<n; i++) {cin >> k;rx = build(rx,k);}work1(rx);mp[p] = 1;while(l--) {Node *ry=new Node;ry = NULL;q.clear();for(int j=0; j<n; j++) {cin >> k;ry = build(ry,k);}work2(ry);mp[q]==1?puts("Yes"):puts("No");}}return 0;
}