方法1：
① 找根：基于先序序列的首元素即是根，找出樹(shù)的根。
② 劃分子問(wèn)題：基于中序序列、根和先序序列，劃分出左右子樹(shù)的中序和先序序列。
③ 治理子問(wèn)題：基于左右子樹(shù)的中序和先序序列，遞歸的處理左右子樹(shù)。
④ 合并：將左右子樹(shù)根節(jié)點(diǎn)的存儲(chǔ)位置，合并為原樹(shù)的左右子樹(shù)。
⑤ 后序遍歷：基于構(gòu)建出的樹(shù)，進(jìn)行后序遍歷，輸出后序序列。

struct Node{char dat;
	int l,r;
}tr[N];
int tot;
string in,pr;
int build(int ib,int ie,int pb,int pe){int r=++tot;
	tr[r].dat=pr[pb];
	int rps=in.find(tr[r].dat);
	int len=rps-ib;
	if(rps>ib)tr[r].l=build(ib,rps-1,pb+1,pb+len);
	if(rpsif(!r)return;
	ODR(tr[r].l);
	ODR(tr[r].r);
	cout<cin>>in>>pr;
	int r=build(0,in.size()-1,0,pr.size()-1);
	ODR(r);
}

方法2：
在算法1處理過(guò)程中，找到根后先儲(chǔ)存，當(dāng)遞歸處理完左右子樹(shù)后，再輸出根。

string in,pr;
void solve(int ib,int ie,int pb,int pe){char r=pr[pb];
	int rps=in.find(r);
	int len=rps-ib;
	if(rps>ib)solve(ib,rps-1,pb+1,rp+len);
	if(rpscin>>in>>pr;
	solve(0,in.size()-1,0,pr.size()-1);
}

① 找根：基于先序序列的首元素即是根，找出樹(shù)的根。
② 劃分子問(wèn)題：基于中序序列、根和先序序列，劃分出左右子樹(shù)的中序和先序序列。
③ 治理子問(wèn)題：基于左右子樹(shù)的中序和先序序列，遞歸的處理左右子樹(shù)。
④ 合并：將左右子樹(shù)根節(jié)點(diǎn)的存儲(chǔ)位置，合并為原樹(shù)的左右子樹(shù)。
⑤ 層次遍歷：基于構(gòu)建出的樹(shù)，進(jìn)行層次遍歷，輸出層次序列。

struct Node{char dat;
	int l,r;
}tr[N];
int tot;
string in,pr;
int build(int ib,int ie,int pb,int pe){int r=++tot;
	tr[r].dat=pr[pb];
	int rps=in.find(tr[r].dat);
	int len=rps-ib;
	if(rps>ib)tr[r].l=build(ib,rps-1,pb+1,pb+len);
	if(rpscout<queueq;q.push(r);
	Prnt(r);
	while(!q.empty()){int n=q.ront();q.pop();
		if(tr[n].l){	Prnt(tr[n].l);
			q.push(tr[n].l);
		}
		if(tr[n].r){	Prnt(tr[n].r);
			q.push(tr[n].r);
		}
	}
}
int main(){cin>>in>>pr;
	int r=build(0,in.size()-1,0,pr.size()-1);
	bfs(r);
}

通過(guò)中序序列可以得到左子樹(shù)和右子樹(shù)各自所包含的所有節(jié)點(diǎn)，左子樹(shù)的所有節(jié)點(diǎn)中最先
出現(xiàn)在層次遍歷序列中的節(jié)點(diǎn)是左子樹(shù)的根，同理可得右子樹(shù)的根。

string in,l;
int fr(int ib,int ie){for(int i=0;iint r=fr(ib,ie);cout<ib)solve(ib,r-1);
	if(rcin>>in>>l;solve(0,in.size()-1);
}

有一棵二叉樹(shù)，大深度為D，且所有葉子的深度都相同。所有節(jié)點(diǎn)從上到下，從左到右的編號(hào)為1,2,3...,2^D-1.

在結(jié)點(diǎn)1處放一個(gè)小球，它會(huì)往下落，每個(gè)內(nèi)結(jié)點(diǎn)上都有一個(gè)開(kāi)關(guān)（開(kāi)關(guān)的狀態(tài)是false或true），初始時(shí)全部是false狀態(tài)，當(dāng)每次有小球落到這個(gè)結(jié)點(diǎn)上時(shí)，開(kāi)關(guān)的狀態(tài)被改變。

當(dāng)小球達(dá)到一個(gè)內(nèi)結(jié)點(diǎn)時(shí)，如果該結(jié)點(diǎn)的開(kāi)關(guān)狀態(tài)是關(guān)閉的，則小球往左走，否則往右走，直到走到葉子結(jié)點(diǎn)。

如下圖所示：



表示結(jié)點(diǎn)編號(hào)為1,2,3...15，大深度為4的完全二叉樹(shù)，由于初始時(shí)，所有的結(jié)點(diǎn)的開(kāi)關(guān)狀態(tài)是false，所以第一個(gè)球下落時(shí)經(jīng)過(guò)結(jié)點(diǎn)1 2 4最終落在結(jié)點(diǎn)8上，第二個(gè)球下落時(shí)經(jīng)過(guò)結(jié)點(diǎn)1 3 6最終落在結(jié)點(diǎn)12上，第三個(gè)球下落時(shí)，經(jīng)過(guò)結(jié)點(diǎn)1 2 5最終落在結(jié)點(diǎn)10上。

現(xiàn)在給出多組測(cè)試數(shù)據(jù)，最多包含1000組，每組測(cè)試數(shù)據(jù)兩個(gè)值。第一個(gè)值是D，表示二叉樹(shù)的大深度。第二個(gè)值是L，表示小球的個(gè)數(shù)L。

假設(shè)I不超過(guò)整棵樹(shù)的葉子個(gè)數(shù)，2≤D≤20，and 1≤L≤5000

編寫(xiě)一個(gè)程序，計(jì)算出小球從節(jié)點(diǎn)1處依次開(kāi)始下落，最后一個(gè)小球L將會(huì)落下哪里？輸出第L個(gè)小球最后所在的葉子編號(hào)。

輸入格式
第一行一個(gè)整數(shù)n，表示測(cè)試數(shù)據(jù)的組數(shù)

接下來(lái)n行，每行兩個(gè)整數(shù)分別表示二叉樹(shù)的深度D和小球的個(gè)數(shù)L，用空格隔開(kāi)

最后一行，“-1”，表示測(cè)試數(shù)據(jù)結(jié)束

輸出格式
輸出n行，分別表示每組測(cè)試數(shù)據(jù)，第L個(gè)小球最后所在的葉子編號(hào)

輸入輸出樣列
輸入樣例1：
5
4 2
3 4
10 1
2 2
8 128
-1
輸出樣例1：
12
7
512
3
255

這道題就是個(gè)大大大大大氵題，直接按照題目的思路模擬即可。

#include#define debug(x) cout<< #x<< '='<< x<< '\n';
using namespace std;
bool tr[1000010]; //lson=t*2,rson=t*2+1
int T;
void slove(){memset(tr,0,sizeof(tr));
	int D,L;scanf("%d%d",&D,&L);
	int a=(1<int now=1;
		while(now	int t=now;
			if(!tr[now])now=now<<1;
			else now=now<<1|1;
			tr[t]^=1;
		}x=now;
	}
	printf("%d\n",x);
}
int main () {scanf("%d",&T);
	while(T--)slove();
	return 0;
}

農(nóng)夫約翰非常認(rèn)真地對(duì)待他的奶牛們的血統(tǒng).然而他不是一個(gè)真正優(yōu)秀的記帳員.他把他的奶牛們的家譜作成二叉樹(shù),并且把二叉樹(shù)以更線性的”樹(shù)的中序遍歷“和”樹(shù)的前序遍歷“的符號(hào)加以記錄而不是用圖形的方法.

你的任務(wù)是在被給予奶牛家譜的”樹(shù)中序遍歷“和”樹(shù)前序遍歷“的符號(hào)后,創(chuàng)建奶牛家譜的”樹(shù)的后序遍歷“的符號(hào)。每一頭奶牛的姓名被譯為一個(gè)唯一的字母. （你可能已經(jīng)知道你可以在知道樹(shù)的兩種遍歷以后可以經(jīng)常地重建這棵樹(shù).）顯然,這里的樹(shù)不會(huì)有多余 26 個(gè)的頂點(diǎn).

這是在樣例輸入和 樣例輸出中的樹(shù)的圖形表達(dá)方式：

                 C
                /   \
               /     \
              B       G
             / \     /
            A   D   H
               / \
              E   F
樹(shù)的中序遍歷是按照左子樹(shù)，根，右子樹(shù)的順序訪問(wèn)節(jié)點(diǎn)。

樹(shù)的前序遍歷是按照根，左子樹(shù)，右子樹(shù)的順序訪問(wèn)節(jié)點(diǎn)。

樹(shù)的后序遍歷是按照左子樹(shù)，右子樹(shù)，根的順序訪問(wèn)節(jié)點(diǎn)。

輸入格式
第一行: 樹(shù)的中序遍歷

第二行: 同樣的樹(shù)的前序遍歷

輸出格式
單獨(dú)的一行表示該樹(shù)的后序遍歷.

輸入輸出樣列
輸入樣例1：
ABEDFCHG
CBADEFGH
輸出樣例1：
AEFDBHGC

模板題啊。

#include#define debug(x) cout<< #x<< '='<< x<< '\n';
using namespace std;
string p, i;
void build (string p, string i) {if (p.empty ()) return;
    char r = p[0];
    int k = i.find (r);
    p.erase (p.begin ());
    string l1 = p.substr (0, k);
    string r1 = p.substr (k);
    string l2 = i.substr (0, k);
    string r2 = i.substr (k + 1);
    build (l1, l2);
    build (r1, r2);
    cout<< r;
}
int main () {cin >>i >>p;
    build (p, i);
	return 0;
}

二叉堆使用完全二叉樹(shù)實(shí)現(xiàn)，分為大根堆和小根堆兩種：
大根堆：任意一個(gè)分支結(jié)點(diǎn)的值都大于或者等于其子節(jié)點(diǎn)的值。
小根堆：任意一個(gè)分支結(jié)點(diǎn)的值都小于或者等于其子節(jié)點(diǎn)的值。

插入操作要求在不影響二叉堆性質(zhì)的前提下，在二叉堆中添加一個(gè)新元素。
性質(zhì)1：完全二叉樹(shù)結(jié)構(gòu)，插入新元素后需要繼續(xù)保持完全二叉樹(shù)的結(jié)構(gòu)。
性質(zhì)2：任何一個(gè)分支節(jié)點(diǎn)的值都大于等于(大根堆)或小于等于(小根堆)其子節(jié)點(diǎn)的值。

① 堆尾插入：每次在堆尾插入新元素（確保插入后仍然是完全二叉樹(shù)結(jié)構(gòu)）。
② 向上調(diào)整（和父節(jié)點(diǎn)比較），將新元素調(diào)整到合適的位置。

刪頂操作要求在不影響二叉堆性質(zhì)的前提下，將堆頂元素刪除。
性質(zhì)1：完全二叉樹(shù)結(jié)構(gòu)，刪除堆頂后需要繼續(xù)保持完全二叉樹(shù)的結(jié)構(gòu)。
性質(zhì)2：任何一個(gè)分支節(jié)點(diǎn)的值都大于等于(大根堆)或小于等于(小根堆)其子節(jié)點(diǎn)的值。

① 將堆頂賦值為堆尾元素的值，接著刪除堆尾節(jié)點(diǎn)。（保持完全二叉樹(shù)結(jié)構(gòu)）
② 向下調(diào)整(和孩子節(jié)點(diǎn)比較)，堆頂元素調(diào)整到合適的位置。

插入操作：堆尾添加元素時(shí)間復(fù)雜度O(1)，向上調(diào)整的次數(shù)大為完全二叉樹(shù)的層數(shù)：
log2 n + 1，故插入操作的時(shí)間復(fù)雜度為：O(log2 n )。
刪頂操作：堆頂復(fù)制和堆尾刪除時(shí)間復(fù)雜度O(1)， 向下調(diào)整的次數(shù)大為完全二叉樹(shù)
的層數(shù)： log2 n + 1，故刪頂操作的時(shí)間復(fù)雜度為：O(log2 n )。

int heap[N],tt;
bool empty(){return !tt;}
int sz(){return tt;}
int tp(){return heap[1];}
int psh(int v){heap[++tt]=v;
	int x=tt;
	while(x>1&&heap[x]>1]){swap(heap[x>>1],heap[x]);
		x>>=1;
	}
}
void pop(){heap[1]=heap[tt--];
	int x=1,p=x<<1;
	while(p<=tt){if(p+1<=tt&&heap[p+1]

priority_queue,greater>qg;
priority_queue,less>ql;

q.push(x);

q.pop();

struct Node{int a;
	bool operator<(const Node&W)const{return a>W.a;
	}
}
priority_queue,less>q;

struct Node{int a;
	bool operator<(const Node&W)const{return a,greater>q;

有兩個(gè)長(zhǎng)度都是N的序列A和B，在A和B中各取一個(gè)數(shù)相加可以得到N^2個(gè)和，求這N^2個(gè)和中最小的N個(gè)。

輸入格式
第一行一個(gè)正整數(shù)N；

第二行N個(gè)整數(shù)Ai,滿足Ai<=Ai+1且Ai<=10^9;（i和i+1表示序列的下標(biāo)）

第三行N個(gè)整數(shù)Bi, 滿足Bi<=Bi+1且Bi<=10^9。（i和i+1表示序列的下標(biāo)）

輸出格式
輸出僅一行，包含N個(gè)整數(shù)，從小到大輸出這N個(gè)最小的和，相鄰數(shù)字之間用空格隔開(kāi)。

輸入輸出樣列
輸入樣例1：
3
2 6 6
1 4 8
輸出樣例1：
3 6 7
說(shuō)明
【數(shù)據(jù)規(guī)模】

對(duì)于50%的數(shù)據(jù)中，滿足1<=N<=1000；

對(duì)于100%的數(shù)據(jù)中，滿足1<=N<=100000。

#includeusing namespace std;
typedef pairPII; 
const int N=1e5+10;
int n,a[N],b[N],t[N];
priority_queue,greater>q;
int main(){cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)q.push(make_pair(a[1]+b[i],i)),t[i]=1;
	for(int i=1;i<=n;i++){cout<