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

rhsgfswg

一、 问题本质分析

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

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

二、算法设计思路

• 递归建模：将每次折叠视为二叉树的生长
  
  
  • 左子树代表新产生的下折痕
  • 右子树代表新产生的上折痕
    
    
• 中序遍历：按照"左-根-右"的顺序访问节点
• 空间优化：直接生成结果，无需存储整个树结构
  
  

三、 复杂度分析

• 时间复杂度：O(2^n) 每个节点访问一次
• 空间复杂度：O(n) 递归栈深度
  
  

四、完整代码

1. class FoldPaper {
   
2.   public:
   
3.     vector<string> foldPaper(int n) {
   
4.         vector<string> res;
   
5.         if (n < 1) return res; // 边界条件处理
   
6. 
   
7.         // 模拟折纸过程，实际上是中序遍历二叉树
   
8.         inOrder(1, n, true, res);  // 根节点是下折痕
   
9.         return res;
   
10.     }
    
11. 
    
12.     // 递归实现的中序遍历
    
13.     void inOrder(int i, int n, bool isDown, vector<string>& res) {
    
14.         if (i > n) return; // 递归终止条件
    
15. 
    
16.         inOrder(i + 1, n, true, res); // 遍历左子树（总是下折痕）
    
17.         res.push_bACk(isDown ? "down" : "up");  // 当前节点
    
18.         inOrder(i + 1, n, false, res); // 遍历右子树（总是上折痕）
    
19.     }
    
20. };

复制代码

来源：大矩学习资料
C++