Description
请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展 开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折，对折N次。请从上到下计算出所有折痕的⽅向。
给定折的次数n,请返回从上到下的折痕的数组，若为下折痕则对应元素为”down”,若为上折痕则为”up”.
测试样例：
1
返回：["down"]
Solutions
1. Binary Tree Inorder Travsal
转换成二叉树，先右再中后左的中序遍历。
# -*- coding:utf-8 -*-
# Time: O(n)
# Space: O(1)
class FoldPaper:
def foldPaper(self, n):
res = []
self.inorder(0, n, True, res)
return res
def inorder(self, i, n, is_down, res):
if i >= n:
return
self.inorder(i + 1, n, True, res)
res.append('down' if is_down else 'up')
self.inorder(i + 1, n, False, res)