牛客网4499题解析：折纸问题背后的二叉树原理

一、 问题本质分析

每次对折都会在原有折痕序列的每对相邻折痕之间插入新的折痕，形成如下规律：

• 奇数位置总是"down"

• 偶数位置总是"up" 这实际上构成了一个完全二叉树的中序遍历序列

二、算法设计思路

1. 递归建模：将每次折叠视为二叉树的生长

• 左子树代表新产生的下折痕

• 右子树代表新产生的上折痕

2. 中序遍历：按照"左-根-右"的顺序访问节点

3. 空间优化：直接生成结果，无需存储整个树结构

三、 复杂度分析

• 时间复杂度：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); // 遍历右子树（总是上折痕）
    }
};