L2-004. 這是二叉搜尋樹嗎？
一棵二叉搜尋樹可被遞歸地定義為具有下列性質的二叉樹：對于任一結點，
- 其左子樹中所有結點的鍵值小于該結點的鍵值；
- 其右子樹中所有結點的鍵值大于等于該結點的鍵值；
- 其左右子樹都是二叉搜尋樹。
所謂二叉搜尋樹的“鏡像”，即将所有結點的左右子樹對換位置後所得到的樹。
給定一個整數鍵值序列，現請你編寫程式，判斷這是否是對一棵二叉搜尋樹或其鏡像進行前序周遊的結果。
輸入格式：
輸入的第一行給出正整數N（<=1000）。随後一行給出N個整數鍵值，其間以空格分隔。
輸出格式：
如果輸入序列是對一棵二叉搜尋樹或其鏡像進行前序周遊的結果，則首先在一行中輸出“YES”，然後在下一行輸出該樹後序周遊的結果。數字間有1個空格，一行的首尾不得有多餘空格。若答案是否，則輸出“NO”。
題意：略
思路：首先通過輸入的前兩個數字判斷這棵二叉樹是否是“鏡像”。如果num[0] > num[1]則不是“鏡像”，否則是“鏡像”。然後，下
一步判斷左子樹的元素和右子樹的元素。以非“鏡像”搜尋二叉樹和非二叉搜尋樹為例。
例如：8 6 5 7 10 8 11中8是輸入的第一個元素它就整棵樹的根，然後發現10是第一個大于等于8的元素是以。作為根的8和10之間的元素便是左子樹，從10到末尾的元素就是右子樹。在子樹中的操作也相同。
在 8 6 8 5 10 9 11中第二個元素6比第一個元素8小則該樹不是“鏡像”搜尋二叉樹。第三個元素8是第一個大于等于根的元素。則第一個元素與第三個元素之間的元素就是根8的左子樹。在第三個元素之後包括它本身的就是根的右子樹。但是，在右子樹上有一個元素5小于該子樹的根。是以，它不是二叉搜尋樹。
然後剩下的就是在寫的時候注意細節就行了。
下面是我的AC代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAX 1005
using namespace std;
int n,num[MAX], ans[MAX],aa;
bool ok,OK;
bool Judge(bool a){return a == ok;}
bool Judge2(int now,int head,int rear)
{
return !(rear - head < -1);
}
void Put(int now, int head,int rear)
{
// getchar();
// cout << now << "/" << head << "/" << rear << endl;
int j,i;
if(head >= n || rear >= n || now >= n) return; //如果已經越界則直接傳回。
for(j = head; j <= rear; j++){
if(!Judge(num[j] < num[now])){ //因為“鏡像”和“非鏡像”是在這裡的判斷相反，是以需要Judge函數來判斷。
break;
}
}
for(i = j; i <= rear; i++)
if(Judge(num[i] < num[now])) return;
//因為這棵（子）樹是以now為根的子樹，now到j之間的元素就是對應的左子樹，j到rear之間的元素就是對應的右子樹
if(Judge2(head,head+1,j-1)){ //在這裡使用Judge2就是一個細節上的處理沒有這個判斷會被 5 1 6 9 8 7 這組資料卡住。
Put(head,head+1,j-1);
ans[aa++] = num[head];
}
if(Judge2(j,j+1,rear)){
Put(j,j+1,rear);
ans[aa++] = num[j];
}
return;
}
int main( )
{
while(cin >> n){
memset(num,0,sizeof(num));
for(int j = 0; j < n; j ++)
cin >> num[j];
if(num[0] > num[1]) ok = true; //通過前兩個元素判斷是否是“鏡像”
else ok = false;
aa = 0;
memset(ans,0,sizeof(ans));
Put(0,1,n-1);
ans[aa++] = num[0];
if(aa < n-1){
cout << "NO" << endl;
}else{
cout << "YES" << endl;
cout << ans[0];
for(int j = 1; j < aa; j++)
cout << " " << ans[j];
cout << endl;
}
}
return 0;
}
我剛開始看完的第一反應就是模拟而以下二叉樹就行了，但是，一想那樣做有些麻煩。于是，就自己想了一個在debug中更麻煩的做法......在AC後上網查了一下别人代碼思路上也是模拟。但是，他們很多是還原二叉樹然後在進行一系列的操作。我感覺這樣有些小小的麻煩。
L2-011. 玩轉二叉樹
給定一棵二叉樹的中序周遊和前序周遊，請你先将樹做個鏡面反轉，再輸出反轉後的層序周遊的序列。所謂鏡面反轉，是指将所有非葉結點的左右孩子對換。這裡假設鍵值都是互不相等的正整數。
輸入格式：
輸入第一行給出一個正整數N（<=30），是二叉樹中結點的個數。第二行給出其中序周遊序列。第三行給出其前序周遊序列。數字間以空格分隔。
輸出格式：
在一行中輸出該樹反轉後的層序周遊的序列。數字間以1個空格分隔，行首尾不得有多餘空格。
題意：略
思路：基本思路和上面題一樣也是模拟。如果隻是單純的輸出層序周遊很容易。但是，要輸出反轉後的層序周遊這個就有點麻煩了。隻是代碼實作也和上面的做法差不多。也是确定左子樹和右子樹是哪段數組。
下面是我的AC代碼：
#include<iostream>
#define MAX 35
using namespace std;
int num1[MAX],num2[MAX];
int n;
struct tree{
int head,rear; //結構體中定義的是這個棵子樹在數組上處于haed~rear之間。
int num; //其中num不是最後輸出的數字，而是存在于num2數組的下标。
};
tree que[MAX];
void BFS( )
{
int head = 0,rear = 0;
tree now = {0,n-1,0};
que[rear++] = now;
tree next;
while(head < rear){
now = que[head++];
if(now.head >= now.rear) continue;
for(int j = now.head; j <= now.rear; j++){
if(num1[j] == num2[now.num]){
if(j < now.rear){ //因為要輸出的是反轉後的層序周遊，是以，加入隊列的順序也有所不同。
next.head = j+1;
next.rear = now.rear;
next.num = now.num + j - now.head + 1;
que[rear++] = next;
}
if(j > now.head){
next.head = now.head;
next.rear = j - 1;
next.num = now.num + 1;
que[rear++] = next;
}
break;
}
}
}
return;
}
int main( )
{
while(cin >> n){
for(int j = 0; j < n; j++)
cin >> num1[j];
for(int j = 0; j < n; j++)
cin >> num2[j];
BFS();
//cout << que[0].num;
/*for(int j = 1; j < n; j++)
cout << " " << que[j].num;
cout << endl;*/
cout << num2[que[0].num];
for(int j = 1; j < n; j++)
cout << " " << num2[que[j].num];
cout << endl;
}
}
在AC後我也在網上看了其他人的代碼其中有一份代碼相當簡短。
來源：http://m.blog.csdn.net/article/details?id=52137710
#include <cstdio>
#include <vector>
using namespace std;
vector<int> in, pre, level(100000, -1);
void levelorder(int root, int start, int end, int index) {
if(start > end) return ;
int i = start;
while(i < end && in[i] != pre[root]) i++;
level[index] = pre[root];
levelorder(root + 1, start, i - 1, 2 * index + 2);
levelorder(root + 1 + i - start, i + 1, end, 2 * index + 1);
}
int main() {
int n, cnt = 0;
scanf("%d", &n);
in.resize(n);
pre.resize(n);
for(int i = 0; i < n; i++) scanf("%d", &in[i]);
for(int i = 0; i < n; i++) scanf("%d", &pre[i]);
levelorder(0, 0, n-1, 0);
for(int i = 0; i < level.size(); i++) {
if(level[i] != -1 && cnt != n - 1) {
printf("%d ", level[i]);
cnt++;
} else if(level[i] != -1){
printf("%d", level[i]);
break;
}
}
return 0;
}
因為，上學期上資料結構課的時候光想着睡覺了，結果看到這個題。就連什麼是前序、中序、後序、層序周遊都廢了很大的勁。以至于現在看上面這個神奇的代碼琢磨了一天才琢磨明白。QAQ......
![關于多項式的一點研究及其在ACM競賽中的應用 關于多項式的一點研究及其在ACM競賽中的應用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)