- 难度：中等
- Microsoft 面试题
题目
折纸，每次都是将纸从右向左对折，凹痕为 0，凸痕为 1，求折 n 次后，将纸展开的折痕组成的 01 序列。
注意事项
- 1 ≤ n ≤ 20
样例
Sample Input:
1
Sample Output:
"0"
Sample Input:
1
Sample Output:
"001"
解答
可以容易写出前 4 项的 01 序列：
0
0 0 1
0 0 1 0 0 1 1
0 0 1 0 0 1 1 0 0 0 1 1 0 1 1
可以看到其中的规律：
- 第 1 条折痕总为 0
- 之后每次在新产生的折痕两侧产生一个凹折痕和一个凸折痕
于是这个序列可以看成是以下二叉树中序遍历的结果：
- 根结点的值为 0
- 每个节点的左子树的根结点值恒为 0，右子树的的根结点的值为 1。
代码如下：
class Solution
{
private:
class TreeNode
{
public:
char val;
TreeNode *left, *right;
TreeNode(char val, TreeNode *left = nullptr, TreeNode *right = nullptr)
: val(val), left(left), right(right) {}
};
string result;
void midOrderTraverse(TreeNode *root)
{
if(root != nullptr)
{
midOrderTraverse(root->left);
result += root->val;
midOrderTraverse(root->right);
}
}
void buildTree(TreeNode *root, int n)
{
root->left = new TreeNode('0');
root->right = new TreeNode('1');
if(n == 1)
return;
else
{
buildTree(root->left, n - 1);
buildTree(root->right, n - 1);
}
}
public:
/**
* @param n: The folding times
* @return: the 01 string
*/
string getString(int n)
{
TreeNode *root = new TreeNode('0');
if(n != 1)
buildTree(root, n - 1);
midOrderTraverse(root);
return result;
}
};
