二叉树-7.11 折纸

题目：

请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展 开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折，对折N次。请从上到下计算出所有折痕的⽅向。

给定折的次数n,请返回从上到下的折痕的数组，若为下折痕则对应元素为"down",若为上折痕则为"up".

思路：

可以自己折纸试一下。折一次是下折痕，两次是“下下上”，三次是“下下上下下上上”，可以发现，每一次折痕，都是在上一次折痕左边加一条下折痕，右边加一条上折痕（这里用红色加粗的字来代表上一次的折痕）。它们正好可以形成一颗满二叉树的中序遍历：

代码：

# -*- coding:utf-8 -*-
 
class FoldPaper:
    def foldPaper(self, n):
        # write code here
        ans = []
        def dfs(level, fold):
            if level > n:
                return
            dfs(level+1, "down")
            ans.append(fold)
            dfs(level+1, "up")
        
        dfs(1, "down")
        return ans