一道微软以前的面试题，题目大概是，用一张长条纸，将其中一面保持对向自己，将它向上对折一次，展开后会有一个凹的折痕，而对折一次时再向上对折一次，展开后有三条折痕，从上到下为凹凹凸，以此类推，求向上对折n次展开后从上至下的凹凸顺序。

思路
如果反复实验会发现一个规律，第一次对折会生成一个凹折痕，此后每次对折会在现有的每个折痕上边加一个凹折痕，下边加一个凸折痕。所以可以用二叉树结构来做这题，对折n次就生成一个高n的满二叉树，头节点为凹，每个左节点为凹，每个右节点为凸，然后来一遍中序遍历打印即可。

代码

include<iostream>

include<string>

include<queue>

using namespace std;

struct Node{
string value;
Node left = NULL;
Node right = NULL;
};
Node getNode(string value);
//根据对折次数返回一颗二叉树
Node getTree(int n){
if(n<1)return NULL; int t = 1; Node *tree = getNode("凹"); queue<pair<Node *,int> > que;
que.push(make_pair(tree,1));
while(t<n){ pair<Node *,int> pair = que.front();
if(pair.second==n)break;
que.pop();
Node tmp = pair.first;
tmp->left = getNode(“凹”);
tmp->right = getNode(“凸”);
que.push(make_pair(tmp->left,pair.second+1));
que.push(make_pair(tmp->right,pair.second+1));
}
return tree;
}
//中序遍历
void midPrint(Node tree){
if(tree==NULL)return;
midPrint(tree->left);
cout << tree->value << “ “;
midPrint(tree->right);
}
int main(){
Node *tree;
int n;
cin >> n;
tree = getTree(n);
midPrint(tree);

return 0;

}
Node getNode(string value){
Node p = new Node();
p->value = value;
return p;
}
但其实可以用更简便的方式，不需要特意生成二叉树，直接把按中序遍历改一下即可，代码如下：

include<iostream>

using namespace std;
//（层数，对折次数也是最大层数，是否打印凹）
void printAllFolds(int i,const int N,bool down){
if(i>N)return;
printAllFolds(i+1,N,true);
cout << (down?”凹”:”凸”);
printAllFolds(i+1,N,false);
}

int main(){
int n;
cin >> n;
printAllFolds(1,n,true);

return 0;

}