這個題我見到過不止一次。筆試面試。

你拿個紙折一折會發現是這樣的：

這棵樹左子樹是紙的下半部分，右子樹是紙的上半部分。

下折痕指的是折痕突起的方向是紙的背面。

可以看出折痕是一棵滿二叉樹，根節點是下折痕，每一棵子樹的左孩子是上折痕，每一棵子樹的右孩子是下折痕。

從紙的上面到下面打印就是二叉樹的RVL（右根左）的遍歷。

對折N次就是指N層節點。

/*** 請把紙條豎著放在桌?上，然后從紙條的下邊向上?對折，壓出折痕后再展開。* 此時有1條折痕，突起的?向指向紙條的背?，這條折痕叫做“下”折痕 ；* 突起的?向指向紙條正?的折痕叫做“上”折痕。如果每次都從下邊向上? 對折，* 對折N次。請從上到下計算出所有折痕的?向。* 給定折的次數n,請返回從上到下的折痕的數組，若為下折痕則對應元素為"down",* 若為上折痕則為"up".* <p>* 從紙的上面到下面打印就是二叉樹的RVL（右根左）的遍歷。** @param n* @return*/
public static String[] foldPaper(int n) {List<String> result = new ArrayList<>();fold(1, n, "down", result);return result.toArray(new String[result.size()]);
}private static void fold(int level, int n, String type, List<String> result) {if (level <= n) {//Rfold(level + 1, n, "down", result);//Vresult.add(type);//Lfold(level + 1, n, "up", result);}
}

?