牛客网4499题解析：折纸问题背后的二叉树原理
https://dajuwangluo.cn/zb_users/upload/2025/07/202507061751792846482952.jpg一、 问题本质分析每次对折都会在原有折痕序列的每对相邻折痕之间插入新的折痕，形成如下规律：
[*]奇数位置总是"down"
[*]偶数位置总是"up" 这实际上构成了一个完全二叉树的中序遍历序列
二、算法设计思路
[*]递归建模：将每次折叠视为二叉树的生长
[*]左子树代表新产生的下折痕
[*]右子树代表新产生的上折痕
[*]中序遍历：按照"左-根-右"的顺序访问节点
[*]空间优化：直接生成结果，无需存储整个树结构
三、 复杂度分析
[*]时间复杂度：O(2^n) 每个节点访问一次
[*]空间复杂度：O(n) 递归栈深度
四、完整代码
class FoldPaper {
public:
vector<string> foldPaper(int n) {
vector<string> res;
if (n < 1) return res; // 边界条件处理
// 模拟折纸过程，实际上是中序遍历二叉树
inOrder(1, n, true, res);// 根节点是下折痕
return res;
}
// 递归实现的中序遍历
void inOrder(int i, int n, bool isDown, vector<string>& res) {
if (i > n) return; // 递归终止条件
inOrder(i + 1, n, true, res); // 遍历左子树（总是下折痕）
res.push_bACk(isDown ? "down" : "up");// 当前节点
inOrder(i + 1, n, false, res); // 遍历右子树（总是上折痕）
}
};
来源：大矩学习资料
C++
页:
[1]