这个为递归的一篇好文可与本文结合的看。

请把一段纸条竖着放在桌子上 然后从纸条的下边向上方对折1次， 压出折痕后展开此时折痕是凹下去的， 即折痕突起的方向指向纸条的背面如果从纸条的下边向上方连续对折2次， 压出折痕后展开 此时有三条折痕， 从上到下依次是下折痕、 下折痕和上折痕给定一个输入参数N， 代表纸条都从下边向上方连续对折N次请从上到下打印所有折痕的方向。

他不是最底层就先插入左节点，然后是自己【因为自己不知道是左还是右所以加入了判断，通过down来记录本身是左节點还是右节点如果down==‘down’打印凹  开始的时候#第一次带入##因为根部是凹，所以从‘down’开始这里打印的就是根节点。】然后是右节点

【因為自己不知道是左还是右，所以加入了判断通过down来记录本身是左节点还是右节点，如果down==‘down’打印凹】

开始的时候#第一次带入##因为根部是凹所以从‘down’开始，这里打印的就是根节点

中序遍历，左中右当前节点函数，先遍历左边遍历当前，打印遍历右边。

用了N个空間遍历了2^n-1的功能