|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> using namespace std; int dlr[1005],ldr[1005],cnt,vis[1005]; stack<int> lrd; int finddlr(int target){ for (int i = 0; i < cnt; i++) if (dlr[i] == target) return i; return 0; } int findldr(int target){ for (int i = 0; i < cnt; i++) if (ldr[i] == target) return i; return -1; } int findlen(bool right,int pos){ //true for right false for left if (right) { for (int i = pos+1; i < cnt; i++) if (vis[i]) return i-pos-1; return cnt-pos-1; }else{ for (int i = pos-1; i >= 0;i--) if (vis[i]) return pos-i-1; return pos; } } void genlrd(int root){ lrd.push(root); int a = finddlr(root); int b = findldr(root); vis[b] = true; int ltlen = findlen(false,b); int rtlen = findlen(true,b); int ltroot = dlr[a+1]; int rtroot = dlr[a+ltlen+1]; if (rtlen) genlrd(rtroot); if (ltlen) genlrd(ltroot); } int main(int argc, char *argv[]){ while (cin >> cnt) { memset(dlr, 0, sizeof(dlr)); memset(ldr, 0, sizeof(ldr)); memset(vis, 0, sizeof(vis)); while (!lrd.empty()) lrd.pop(); for (int i = 0; i < cnt; i++) cin >> dlr[i]; for (int i = 0; i < cnt; i++) cin >> ldr[i]; genlrd(dlr[0]); while (!lrd.empty()) { cout << lrd.top(); if (lrd.size() != 1) cout << " "; lrd.pop(); } cout << endl; } return 0; } |
这道题是已知DLR和LDR，求LRD。
DLR（先序）具有的特点是根节点一定在它连接的子树的左边，子树的根节点一定在子树的子树的左边，LDR的特点是投影，就是下面这个图：
接下来就拿样例举例子 ：
这个的DLR是1 2 4 7 3 5 8 9 6
这个可以分段看，首先是 1/247/35869，然后可以发现1是root，247又可以分成2/47/～三段（～表示没有节点），在这里2是这个子树的根，35896又可以分为3/589/6在这里3是右边子树的根，589是左半部分，6是右半部分，就这样一直分下去就可以发现DLR的特点了，而这种特点正是因为DLR是DFS生成的。
然后看LDR，4 7 2 1 8 5 9 3 6
这个也是分段，首先472/1/85936，你会发现如果知道根的话，那么这个根左边有什么右边有什么都是可以从LDR里看出来的。
所以我们这个题就可以先找到总根（DLR第一位），然后在LDR里找到根的位置，想办法确定左右肢的元素个数，然后回到DLR里找到左右肢的根，分别把它们当作总根递归下去，这样我们就能还原出树的全貌了，而这个题更简单一点，你只要以DRL的顺序这么递归，把每一次找到的根都压入stack里，最后再逐个弹出输出，正好就是LRD了。
如果已知LRD和LDR，是可以求出DLR的，方法和这个差不太多。但是如果知道DLR喝LRD，想求LDR做不到，LDR不止一个解。
January 18, 2015
void go(int pl,int pr,int ml,int mr){
last.push(pre[pl]);
int i;
for(i=ml;i<=mr;i++)
if(pre[pl]==mid[i]){
int pp=pl+i-ml+1;
if( pp<=pr && i<pr ) go(pp,pr,i+1,mr);
if(pl+1<=pp-1&&ml<i) go(pl+1,pp-1,ml,i-1);
break;
}
}