請把一段紙條豎著放在桌子上，然后從紙條的下邊向上方對折1次，壓出折痕后展開，此時折痕是凹下去的，即折痕突起的方向指向紙條的背面， 如果從紙條的下邊向上方連續對折2次，壓出折痕后展開，此時有三條折痕，從上到下依次是下折痕、下折痕和上折痕，
給定一個輸入引數N，代表紙條都從下邊向上方連續對折N次， 請從上到下列印所有折痕的方向，
例如:N=1時，列印: down N=2時，列印: down down up
根據題目要求，我實際折了一把，并且每一次折的時候，我都進行了標注：1凹，代表第一次折的， 2 凹或者2凸代表第二次折的，依次類推.....
觀察了上圖，確實停迷惑人的，下圖我通過繪圖的形式，更加直觀的呈現這個問題的本身
通過手動繪制的圖片，我們按照折紙的先后順序，發現每次折紙，都會在之前的折紙痕跡左右再生出2道痕跡：
第一次折： 1 凹
第二次折： 1 凹兩側生出了 2凹 和 2凸
第三次折: 2凹 和 2凸兩側又生成了 3凹 和 3 凸
依次類推.........
最終我們發現，這就是一顆滿二叉樹，而想要從上到下列印這張紙的痕跡，實際上就是中序遍歷整顆二叉樹的節點，代碼如下
package code03.二叉樹_02; /** * 請把一段紙條豎著放在桌子上，然后從紙條的下邊向上方對折1次，壓出折痕后展開，此時折痕是凹下去的，即折痕突起的方向指向紙條的背面， * * 如果從紙條的下邊向上方連續對折2次，壓出折痕后展開，此時有三條折痕，從上到下依次是下折痕、下折痕和上折痕， * * 給定一個輸入引數N，代表紙條都從下邊向上方連續對折N次， 請從上到下列印所有折痕的方向， * * 例如:N=1時，列印: down N=2時，列印: down down up */ public class Code03_PaperTree { /** * @param times 代表折了幾次紙，也代表二叉樹的層數 * @param n 代表二叉樹的層數 * @param down 凹代表true，凸代表false */ public void process (int times, int curTimes, boolean down) { //上一層已經是最下方的層數，沒有下掛節點了 if (curTimes > times) { return; } //根據觀察，每一層的左節點都是凹 process(times, curTimes + 1, true); System.out.print(down ? "down " : "up "); //每一層的右節點都是凸 process(times, curTimes + 1, false); } public void paperOut (int times) { //times小于1，代表沒折紙 if (times < 1) { return; } //系統記錄折紙的次數, 用來與times作比較用 int curTimes = 1; //第一次默認是凹下去的 process(times, curTimes, true); } public static void main(String[] args) { Code03_PaperTree test = new Code03_PaperTree(); int times = 2; //折紙次數 test.paperOut(times); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/544674.html
標籤：Java