? ? 1從上往下打印二叉樹

【題目】從上往下打印出二叉樹的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。

【考察點(diǎn)】舉例讓抽象具體化；二叉樹

【思路】用ArrayList創(chuàng)建兩個(gè)集合，一個(gè)用來(lái)存儲(chǔ)每個(gè)節(jié)點(diǎn)的值，一個(gè)用來(lái)模仿棧，按照從上到下從左到右的順序?qū)⒐?jié)點(diǎn)入棧。

【錯(cuò)誤1】第一個(gè)集合類型是<Integer>，第二個(gè)集合的類型是<TreeNode>，一定要注意別寫錯(cuò)了哦~

【錯(cuò)誤2】第二個(gè)集合只是模仿棧，但是我弄假成真稀里糊涂真的把它當(dāng)做棧來(lái)用，調(diào)用了棧的方法。。。

【代碼】

????2二叉搜索樹的后序遍歷序列

【題目】輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。

【考察點(diǎn)】舉例讓抽象具體化；二叉樹

【思路】BST的后序序列的合法序列是，對(duì)于一個(gè)序列S，最后一個(gè)元素是x （也就是根），如果去掉最后一個(gè)元素的序列為T，那么T滿足：T可以分成兩段，前一段（左子樹）小于x，后一段（右子樹）大于x，且這兩段（子樹）都是合法的后序序列。每次去掉序列的最后一個(gè)元素，并將前面的元素分成兩段繼續(xù)遞歸。

【錯(cuò)誤1】遞歸時(shí)兩段元素的起止位置一定要弄清楚，改了好幾次才改對(duì)。

【錯(cuò)誤2】切記序列的最后一個(gè)元素不參與循環(huán)，也不參與遞歸，因?yàn)樗钱?dāng)前的root元素。

【錯(cuò)誤3】遞歸的終止條件之一是(start<end)，手誤寫成>了還找了半天問(wèn)題在哪里。。。

【tips】理不清的時(shí)候自己寫一個(gè)測(cè)試用例，跟著用例來(lái)編寫思路會(huì)清晰很多！

【代碼】

????3二叉樹中和為某一值的路徑

【思路】遞歸！若當(dāng)前根節(jié)點(diǎn)不為null，則將它加入a序列。每次遞歸到葉節(jié)點(diǎn)后要將a序列中的最后一個(gè)節(jié)點(diǎn)刪掉，以便返回上層繼續(xù)尋找其它路徑。

【考察點(diǎn)】舉例讓抽象具體化；二叉樹

【錯(cuò)誤1】注意審題，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)才算一條路徑，所以將a加入all的條件有三個(gè)。

【錯(cuò)誤2】在遍歷完一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)后，要在a中remove當(dāng)前節(jié)點(diǎn)，這個(gè)是很關(guān)鍵很關(guān)鍵的一步。

【關(guān)鍵】遞歸特別容易思路混亂，我特意把遞歸的過(guò)程畫了一張圖，這樣思路就清晰了：

【代碼】