二叉樹解題整體框架：

? ? ? ? 1、確定當前題型是做高度還是深度還是搜索樹還是其他

? ? ? ? ? ? ? ? 高度（從下往上，求根深度、高度等）：

? ? ? ? ? ? ? ? ? ? ? ? 使用后序遍歷會更加簡單，遞歸方法一般需要返回值返回上級，讓上級對返回值進行判斷處理;

? ? ? ? ? ? ? ? 深度（從上往下，路徑問題等）

? ? ? ? ? ? ? ? ? ? ? ? 使用前序遍歷會更加簡單，遞歸方法一般需要與回溯一起使用，但是在遞歸的結束階段可能需要額外的判斷內容（在單層邏輯左右子節點遞歸完需要進行回溯處理,同時在此處判斷是不是存在子節點）

? ? ? ? ? ? ? ? 搜索樹

? ? ? ? ? ? ? ? ? ? ? ? 搜索樹通過中序遍歷可以變成一個從小到大的數組

? ? ? ? ? ? ? ? 其他

? ? ? ? ? ? ? ? ? ? ? ? 按照遞歸思路解題即可

? ? ? ? 2、使用遞歸的思路：

? ? ? ? ? ? ? ? （1）確定遞歸的返回值、輸入值（返回值的類型，輸入值的類型可以邊做邊添加）

? ? ? ? ? ? ? ? （2）確定遞歸的停止邏輯（當節點走到哪里就該返回或者停止）

? ? ? ? ? ? ? ? （3）確定遞歸的單層邏輯（根據前中后序或者層序遍歷）

? ? ? ? 3、使用迭代的思路：

? ? ? ? ? ? ? ? （1）如果題型可以使用一個隊列將其左或右節點輸入，然后進行隊頭元素的輸出 就可以使用迭代的思想

? ? ? ? 4、使用前序遍歷+回溯的思路（需要注意3點）：

? ? ? ? ? ? ? ? 一般是從上往下，需要注意以下問題：

? ? ? ? ? ? ? ? （1）遞歸返回值、輸入值：

? ? ? ? ? ? ? ? ? ? ? ? 一般前序遍歷是沒有返回值，使用全局變量進行記錄，如果需要返回值（true or false）需要在停止條件處進行返回對應的返回值，在單層邏輯的時候，仍舊按照先記錄當前節點，使用變量獲取左右遞歸的返回值，最后再根據返回值判斷當前節點的返回值

? ? ? ? ? ? ? ? ? ? ? ? 輸入值一般需要是引用，因為要回溯

? ? ? ? ? ? ? ? （2）遞歸的停止、判斷條件

? ? ? ? ? ? ? ? ? ? ? ? 前序遍歷的遞歸停止條件一般是當前節點是不是葉子節點，與后序遍歷（當前節點是不是空節點不同）

? ? ? ? ? ? ? ? ? ? ? ? 前序遍歷的返回條件無法判斷根節點是不是空節點：需要在主函數中進行額外的判斷

? ? ? ? ? ? ? ? ? ? ? ? 前序遍歷的返回條件無法判斷一個節點是不是空節點：需要在單層遞歸條件中額外的判斷當前節點存在左子節點才進行左子節點的遞歸，存在右子節點才進行右子節點的遞歸，避免出現一個節點有一個空的子節點一個不空的子節點-->尋找空節點的子節點導致報錯

? ? ? ? ?5、二叉搜索樹的思路

? ? ? ? ? ? ? ? （1）對二叉搜索樹中序遍歷是一個有序的數組（實在做不出可以使用）

? ? ? ? ? ? ? ? （2）對二叉搜索樹中序遍歷

????????????????????????要注意：中序遍歷是無法找到上一個節點位置的，所以需要建立一個全局節點去記錄上一個節點（包括了二叉搜索樹變成累加樹中的逆中序）

? ? ? ? ? ? ? ? （3）要知道二叉搜索樹的性質，可以達到從上往下按照已知的路徑遍歷，無需將所有路徑進行遍歷，通過返回新的當前節點來更新整棵二叉搜索樹。

? ? ? ? ? ? ? ??

---

---

一、二叉樹基礎（算法11天）：

? ? ? ? 1、二叉樹的定義

? ? ? ? 2、根節點、子節點、葉子節點、度、節點深度、高度、層、子樹

? ? ? ? 3、二叉樹性質（4條）

? ? ? ? 4、滿二叉樹、完全二叉樹、二叉搜索樹、平衡二叉搜索樹（AVL）

? ? ? ? 5、二叉樹的存儲方式

? ? ? ? ? ? ? ? 鏈式存儲是使用指針指向左右子節點

? ? ? ? ? ? ? ? 順序存儲的子節點位置

二、二叉樹的遍歷方式（算法11天）

? ? ? ? 1、深度優先

????????????????前序（遞歸、迭代）中左右-->適合從上往下，深度，可能結合回溯，在遞歸的終止需要額外判斷；迭代使用棧，根據棧的先進后出，需要先輸入右節點再輸入左節點

????????????????中序（遞歸、迭代）左中右-->適合二叉搜索樹

????????????????后序（遞歸、迭代）左右中-->適合從下往上，高度，遞歸一般需要返回值；迭代就是前序遍歷中右左之后reverse

? ? ? ? 2、廣度優先

????????????????遞歸（需要加深度depth）

????????????????迭代（必須掌握，隊列）

三、二叉樹題型

? ? ? ? 1、翻轉二叉樹（算法12天）

? ? ? ? ? ? ? ? 前序、后序(遞歸迭代都行)層序遍歷（遞歸迭代都行）重點是使用swap交換兩個子節點

? ? ? ? 2、對稱二叉樹（算法12天）

? ? ? ? ? ? ? ?遞歸：

? ? ? ? ? ? ? ? ? ? ? ? 遞歸重點在于理解需要同時處理左右兩個子節點的對稱位置，從下到上判斷是否對稱-->需要返回值，類似于后序遍歷，先處理左右，再處理中（要注意停止、返回條件）

? ? ? ? ? ? ? ? 迭代：

? ? ? ? ? ? ? ? ? ? ? ? 使用隊列記錄兩個節點，但是同時判斷兩個節點的狀態。

? ? ? ? 3、二叉樹的最大深度（算法12天）

? ? ? ? ? ? ? ? 遞歸（迭代）：深度是從上往下，屬于是前序遍歷（前序+回溯），但是最大深度，就相當于求高度，可以使用后序遍歷更簡單（左右中-->通過返回值記錄最大深度）

? ? ? ? 4、二叉樹的最小深度（算法12天）

? ? ? ? ? ? ? ? 遞歸：與最大深度類似，但是不同。

? ? ? ? ? ? ? ? ????????重點在于：深度是當前節點到葉子節點的距離（最小深度是找到最近的葉子節點，當單邊是nullptr，另一邊不是nullptr時，不是葉子節點，不能從當前節點到nullptr，而是到另外有子節點的邊）????????

? ? ? ? ? ? ? ? 迭代：

????????????????????????同樣使用隊列（層序遍歷）使用int depth記錄深度，當前節點沒有子節點就返回深度，有子節點就繼續向隊列中添加元素。

? ? ? ? 5、平衡二叉樹（算法13天）

? ? ? ? ? ? ? ? 題重點：平衡二叉樹就是左右子樹高度最多相差1

? ? ? ? ? ? ? ? 遞歸：

? ? ? ? ? ? ? ? ? ? ? ? 高度題：使用后序遍歷-->左右中，返回值是高度，遞歸左右，在中判斷左右的值：使用一個標志位-1表示高度差超過了1，有-1返回-1，沒-1返回最大的高度

? ? ? ? 6、二叉樹所有的路徑（算法13天）

? ? ? ? ? ? ? ? 遞歸：

? ? ? ? ? ? ? ? ? ? ? ? 路徑問題：從上往下開始遍歷：前序遍歷+回溯。

? ? ? ? ? ? ? ? ? ? ? ? 難點：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）注意前序遍歷一般沒有返回值，是在停止條件處寫入全局變量

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）將int轉換成string:to_string()

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （3）將string轉換成int:stoi()

? ? ? ? ? ? ? ? ? ? ? ? 錯點：因為要進行回溯：說明要傳入的參數是引用而不是復制一個副本！！！！

? ? ? ? 7、左葉子之和（算法13天）

? ? ? ? ? ? ? ? 遞歸：后序遍歷

? ? ? ? ? ? ? ? 難點：理解左葉子：當前節點的左子節點的左右子節點為空

? ? ? ? 8、二叉樹左下角的值（算法14天）

? ? ? ? ? ? ? ? 難點：

????????????????????????理解左下角：最深層 的第一個

? ? ? ? ? ? ? ? 層序遍歷簡單:

????????????????????????只需要獲取每一次迭代的隊列中的隊頭元素

? ? ? ? ? ? ? ? 遞歸：

????????????????????????使用前序遍歷+回溯，記錄vector中最大的路徑長度（深度）

? ? ? ? 9、二叉樹路徑總和，存在目標值（算法14天）

? ? ? ? ? ? ? ? 前序遍歷+回溯的應用

? ? ? ? ? ? ? ? 注意點：

? ? ? ? ? ? ? ? ? ? ? ? 前序遍歷也可以有返回值，返回值是在當前節點設置完后，對左右子節點遞歸獲得的，之后再根據返回值設置當前節點的返回

? ? ? ? ? ? ? ? ? ? ? ? 因為前序遍歷，停止條件為當前節點為葉子節點，沒有討論當前根節點為空，所以要注意root==nullptr的情況；沒有討論當前節點的子節點一個為空一個不空的情況，所以需要再單層遞歸邏輯中額外判斷是否存在子節點。

? ? ? ? 10、二叉樹路徑總和，全部路徑（算法14天）

? ? ? ? ? ? ? ? 前序遍歷+回溯，不需要返回值了，統一記錄即可

? ? ? ? 11、從中序遍歷與后序遍歷構建二叉樹(算法14天)

? ? ? ? ? ? ? ? 理解：中序遍歷、后序遍歷的意義

? ? ? ? ? ? ? ? ? ? ? ? 后序遍歷：左右中，說明數組最后的是中點

? ? ? ? ? ? ? ? ? ? ? ? 中序遍歷：左中右，可以找到左數組、右數組

? ? ? ? ? ? ? ? 遞歸：構建二叉樹（從上往下）-->前序遍歷，需要返回值-->返回值是當前節點的左子樹、右子樹

? ? ? ? ? ? ? ? 難點：如何將vector數組劃分成兩份：

? ? ? ? ? ? ? ? ? ? ? ? vector<int>left(.begin(),.begin()+i);

? ? ? ? ? ? ? ? ? ? ? ? 使用一個新定義的vector數組去獲取原來的數組的一部分

? ? ? ? 12、最大二叉樹（算法15天）

? ? ? ? ? ? ? ? （類似于11題）遞歸：前序遍歷、返回值是子樹。

? ? ? ? 13、合并二叉樹（算法15天）

? ? ? ? ? ? ? ? 同時遞歸兩個二叉樹，屬于構造二叉樹問題-->從上往下前序遍歷，

? ? ? ? ? ? ? ? 1、返回值是子樹，輸入值是兩個二叉樹節點：

? ? ? ? ? ? ? ? 2、停止條件：雙方都為空返回nullptr、有一方為空返回另一方

? ? ? ? ? ? ? ? 3、單層遞歸邏輯：構造新節點，將兩個二叉樹的值添加到新節點中，遞歸兩棵二叉樹的左右子節點作為左右子樹。

? ? ? ? 14、二叉搜索樹中的搜索（算法15天）

? ? ? ? ? ? ? ? 性質：二叉搜索樹左子樹都比當前節點小，右子樹都比當前節點大、

? ? ? ? 15、驗證二叉搜索樹（算法15天）

? ? ? ? ? ? ? ? 錯誤：前序遍歷比較當前值與子節點的大小，返回值true or false，無法保證左子樹所有元素都比右子樹的元素小

? ? ? ? ? ? ? ? 要使用中序遍歷：將二叉搜索樹變成一個數組，或者直接使用中序遍歷進行遍歷判斷大小（但是因為中序遍歷過程并不按照樹的結構從上到下或者從下到上，所以需要一個值去記錄上一個值的大小）

? ? ? ? 16、二叉搜索樹的最小絕對差（算法16天）

? ? ? ? ? ? ? ? 思路1：中序遍歷變成數組，遍歷數組找到最小值? ? ? ?

? ? ? ? ? ? ? ? 思路2：在中序遍歷中去比較獲得最小值

? ? ? ? ? ? ? ? 重點：中序遍歷需要使用一個全局節點去記錄上一個節點的信息。?

????????17、二叉搜索樹中的眾數（算法16天）

? ? ? ? ? ? ? ? 仍舊是利用二叉搜索樹的性質：中序遍歷從小到大：

? ? ? ? ? ? ? ? 數組、直接在中序遍歷中操作

? ? ? ? ? ? ? ? 重點：需要考慮有多個眾數的情況：眾數使用vector數組保存

? ? ? ? 18、二叉搜索樹的最近公共祖先（算法16天）

? ? ? ? ? ? ? ? 理解：最近公共祖先：兩個節點可能有一個是祖先、兩個節點都不是祖先

? ? ? ? ? ? ? ? 使用后序遍歷：通過遞歸左右字節點去獲取左右子樹的返回值；停止條件：當到空節點、找到一個p或者q? ? ?

? ? ? ? 19、二叉搜索樹的最近公共祖先（算法17天）

? ? ? ? ? ? ? ? 與18題不同，這個是針對二叉搜索樹的性質進行尋找

? ? ? ? ? ? ? ? 返回值：返回公共祖先

? ? ? ? ? ? ? ? 從上往下遍歷，當前節點的值在兩個值之間說明當前節點就是最近公共祖先

? ? ? ? ? ? ? ? 當前節點的值在大于兩個值，說明需要向左子樹遍歷，返回左子樹的值

????????????????當前節點的值在小于兩個值，說明需要向右子樹遍歷，返回右子樹的值

? ? ? ? 20、二叉搜索樹中的插入操作（算法17天）

? ? ? ? ? ? ? ? 理解插入的本質：最簡單的插入是不破壞二叉搜索樹的結構，在合適的節點的子節點（空節點）插入需要插入的值

? ? ? ? ? ? ? ? 返回值：可以是當前值（由nullptr-->val）

? ? ? ? 21、刪除二叉搜索樹中的節點（算法17天）

? ? ? ? ? ? ? ? 理解刪除的本質以及后果：

? ? ? ? ? ? ? ? ? ? ? ? 通過二叉搜索樹的性質從上往下找到要刪除的節點，判斷節點的類型：

? ? ? ? ? ? ? ? ? ? ? ? （1）空，返回空

? ? ? ? ? ? ? ? ? ? ? ? （2）葉子，返回空

? ? ? ? ? ? ? ? ? ? ? ? （3）子節點一個有值，一個空，返回有值子樹

? ? ? ? ? ? ? ? ? ? ? ? （4）子節點全部有值，將右子樹接上，左子樹放到右子樹的最左下位置

? ? ? ? 22、修剪二叉搜索樹（算法18天）

? ? ? ? ? ? ? ? 理解修剪的定義：

????????????????????????找到一個范圍，使得二叉搜索樹中所有值都在這個范圍中，不改變樹的整體結構（無法使用中序變數組、數組減枝、數組變二叉搜索樹）

? ? ? ? ? ? ? ? 通過二叉搜索樹的性質，向下進行遞歸，判斷

? ? ? ? ? ? ? ? ? ? ? ? （1）當前節點<最小值：說明當前節點以及左子樹全部去掉，對右子樹進行查找有沒有符合區間的值，返回的是符合區間的值（更新后的當前節點的值）

? ? ? ? ? ? ? ? ????????（2）當前節點>最大值：說明當前節點以及右子樹全部去掉，對左子樹進行查找有沒有符合區間的值，返回的是符合區間的值（更新后的當前節點的值）

? ? ? ? ? ? ? ? ????????（3）當前節點在區間內，對左右子節點進行遞歸，去除不符合的節點，返回當前更新后的節點。

? ? ? ? 23、有序數組轉化為二叉搜索樹（算法18天）

? ? ? ? ? ? ? ? ? ? ? ? 數組二分法

? ? ? ? 24、二叉搜索樹轉換為累加樹（算法18天）

? ? ? ? ? ? ? ? 理解累加樹：

????????????????????????當前節點的值+所有比當前節點值大的值

? ? ? ? ? ? ? ? 逆中序遍歷：

????????????????????????將當前值與前一個值進行相加，所以需要一個全局變量去記錄前一個值

? ? ? ? ? ? ? ??