题目
一道微软以前的面试题,题目大概是,用一张长条纸,将其中一面保持对向自己,将它向上对折一次,展开后会有一个凹的折痕,而对折一次时再向上对折一次,展开后有三条折痕,从上到下为凹凹凸,以此类推,求向上对折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;
}