1，二叉树四种遍历，2，string 去重（去空格）3,根据二叉树后序和中序，求先序；4,已知二叉树后序和中序，求层序；5，蒙德里安的梦想（状态压缩dp）
void InorderTraversal( BinTree BT )//中序
{if(BT==NULL)return;InorderTraversal(BT->Left);printf(" %c",BT->Data);InorderTraversal(BT->Right);
}
void PreorderTraversal( BinTree BT )//先序
{if(BT==NULL)return;printf(" %c",BT->Data);PreorderTraversal(BT->Left);PreorderTraversal(BT->Right);
}
void PostorderTraversal( BinTree BT )//后序
{if(BT==NULL)return;PostorderTraversal(BT->Left);PostorderTraversal(BT->Right);printf(" %c",BT->Data);
}
void LevelorderTraversal( BinTree BT )//层序
{BinTree temp[1100];int in=0;int out=0;temp[in++]=BT;while(in>out){if(temp[out]){printf(" %c",temp[out]->Data);temp[in++]=temp[out]->Left;temp[in++]=temp[out]->Right;}out++;}
}
void PreorderPrintLeaves( BinTree BT )//先序输出叶子节点
{if(BT){if(!BT->Left&&!BT->Right)printf(" %c",BT->Data);PreorderPrintLeaves(BT->Left);PreorderPrintLeaves(BT->Right);}
}
2，去空格
rep1(i,0,n){if(s1[i]==' ')s1.erase(i,1);if(s2[i]==' ')s2.erase(i,1);}erase（x，len）是从x位置开始，删去len长度；
函数调用中，对数组加一个常数的操作时对数组进行裁剪？
3，知中序，后序求先序；
#include<bits/stdc++.h>
#define rep1(i,a,n) for(register int i=a;i<n;i++)
#define rep2(i,a,n) for(register int i=a;i<=n;i++)
#define per1(i,n,a) for(register int i=n;i>a;i--)
#define per2(i,n,a) for(register int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
int n;
int post[10000],mid[10000];
void dfs(int *post,int *mid,int x)
{if(x>0){int root;root=post[x-1];cout<<" "<<root; rep1(i,0,x){if(root==mid[i]){dfs(post,mid,i);dfs(post+i,mid+i+1,x-i-1);return;}}}
}
signed main()
{quick_cin();cin>>n;rep1(i,0,n)cin>>post[i];rep1(i,0,n)cin>>mid[i];cout<<"Preorder:";dfs(post,mid,n);return 0;
}4，求层序
试着直接改编3，的板子，来求层序，但是实现的话比较麻烦，还不如直接利用先序来建个树，对树求层序就比较简单了，当然，3，也可以这样做，先求树，再求先序，但我毕竟是根据先序键树的，能直接输出先序，就不用建树了；
所以既然是根据先序建树，那我可以直接用3，的板子，稍作修改就可；
主要是dfs，新增两个参数，一个是用来建树用到的父节点，一个是区分左右节点的char类型；
还是比较好写的；
void dfs(int *post,int *mid,int x,int father,char c)
{if(x>0){int root=post[x-1];if(c=='l')pp[father].first=root;if(c=='r')pp[father].second=root;rep1(i,0,x){if(root==mid[i]){dfs(post,mid,i,root,'l');dfs(post+i,mid+i+1,x-i-1,root,'r');return;}}}
}#include<bits/stdc++.h>
#define rep1(i,a,n) for(register int i=a;i<n;i++)
#define rep2(i,a,n) for(register int i=a;i<=n;i++)
#define per1(i,n,a) for(register int i=n;i>a;i--)
#define per2(i,n,a) for(register int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
int n;
const int N=1e3+10;
int post[10000],mid[10000];
queue<int>q;
PII pp[N];
void dfs(int *post,int *mid,int x,int father,char c)
{if(x>0){int root=post[x-1];if(c=='l')pp[father].first=root;if(c=='r')pp[father].second=root;rep1(i,0,x){if(root==mid[i]){dfs(post,mid,i,root,'l');dfs(post+i,mid+i+1,x-i-1,root,'r');return;}}}
}
signed main()
{quick_cin();cin>>n;rep1(i,0,n)cin>>post[i];rep1(i,0,n)cin>>mid[i];dfs(post,mid,n,post[n-1],'0');q.push(post[n-1]);cout<<post[n-1];while(q.size()){int t=q.front();if(t!=post[n-1])cout<<" "<<t;q.pop();if(pp[t].first)q.push(pp[t].first);if(pp[t].second)q.push(pp[t].second);}return 0;
}5，蒙德里安的梦想
题意：
核心：（数据范围很小，可以用二进制数表示状态）
先放横着的，在放竖着的 ；这样只要我横着放完，剩下的竖的只要嵌进去就行，所以竖着的只能是这样，即总方案数是横着放的合法方案数；如何判断方案是否合法呢，只需要判断每一列剩下的连续空棋盘数是否为偶数，偶数则合法，否则不合法；
按照闫式dp分析法：
第一步：状态表示：
f[ i , j ] 表示 前i-1列已经放好，从第 i-1 列伸到第 i 列的状态是 j 的所有方案；
属性：数量；
第二步：状态计算：
因为属性是数量，所以f[ i , j ]是所有子集方案之和;
先划分集合：
对于每一行，都有伸或者不伸到第i列两种选择，所以共2^n种方案；
这样划分也是不重不漏的；
这里是表示状态是可以状态压缩的，用个长度为n的二进制数，eg:01000...；表示第二行 伸到第i列，而其他所有行都不伸到第i列的一种方案；
划分好子集后，需要去求子集，进而才能求f[ i , j ]，也就是找状态转移；
既然第 i 列固定了，我们需要看 第i-2 列是怎么转移到到第 i-1列的（看最后转移过来的状态）。假设此时对应的状态是k（第i-2列到第i-1列伸出来的二进制数，比如00100），k也是一个二进制数，1表示哪几行小方块是横着伸出来的，0表示哪几行不是横着伸出来的。
它刚好就是f[ i -1 , k ] , 但是，这个k是有条件限制的，也就是需要是合法的方案；
①k和j不能在同一行，即j&k==0，原因：因为从i-1列到第i列是横着摆放的12的方块，那么i-2列到i-1列就不能是横着摆放的，否则就是1 3的方块了！这与题意矛盾。所以 k和j不能位于同一行！
既然从第i-1列到第i列横着摆的，和第i-2列到第i-1列横着摆的都确定了，那么第i-1列 空着的格子就确定了，这些空着的格子将来用作竖着放。如果 某一列有这些空着的位置，那么该列所有连续的空着的位置长度必须是偶数。
满足这两个条件，f[ i ][ j ] += f[ i-1 ][ k ]；
对这两个条件直接全部枚举可能会tle，这里优化下对条件的筛选；
#include<bits/stdc++.h>
#define rep1(i,a,n) for(register int i=a;i<n;i++)
#define rep2(i,a,n) for(register int i=a;i<=n;i++)
#define per1(i,n,a) for(register int i=n;i>a;i--)
#define per2(i,n,a) for(register int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
int n,m;
const int N=12,M=1<<N;
ll f[N][M];
vector<int>state[M];
bool st[M];
signed main()
{quick_cin();while(cin>>n>>m,n||m){//第一部分：预处理1//对于每种状态，先预处理每列不能有奇数个连续的0rep1(i,0,1<<n){int cnt=0;//记录连续的0的个数bool isvalid=1;// 某种状态没有奇数个连续的0则标记为truerep1(j,0,n)//遍历这一列，从上到下{if(i>>j&1)//i>>j位运算，表示i（i在此处是一种状态）的二进制数的第j位； &1为 //判断该位是否为1，如果为1进入if{if(cnt&1)//这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该 状态不合法{isvalid=0;break;}cnt=0;// 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清 零。//其实清不清零没有影响}else cnt++;}if(cnt&1)isvalid=0;st[i]=isvalid;//状态i是否有奇数个连续的0的情况,输入到数组st中}//下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突rep1(j,0,1<<n) //对于第i列的所有状态{state[j].clear(); //清空上次操作遗留的状态，防止影响本次状态。rep1(k,0,1<<n)//对于第i-1列所有状态{if((j&k)==0&&st[j|k])state[j].pb(k); // 第i-2列伸出来的 和第i-1列伸出来 的不冲突(不在同一行) //解释一下st[j | k] //已经知道st[]数组表示的是这一列没有连续奇数个0的情况，//我们要考虑的是第i-1列（第i-1列是这里的主体）中从第i-2列横插过来的，还要考 虑自己这一列（i-1列）横插到第i列的//比如 第i-2列插过来的是k=10101，第i-1列插出去到第i列的是 j =01000，//那么合在第i-1列，到底有多少个1呢？自然想到的就是这两个操作共同的结果：两个 状态或。 j | k = 01000 | 10101 = 11101//这个 j|k 就是当前 第i-1列的到底有几个1，即哪几行是横着放格子的}}memset(f,0,sizeof f);f[0][0]=1;rep2(i,1,m)rep1(j,0,1<<n)for(auto k:state[j])f[i][j]+=f[i-1][k];cout<<f[m][0]<<endl;}return 0;
}
