Binary Tree - 總結篇
二叉樹的理論基礎
- 關於二叉樹，你該瞭解這些！ (opens new window)：二叉樹的種類、存儲方式、遍歷方式、定義方式
二叉樹的遍歷方式
- 深度優先遍歷
- 廣度優先遍歷
- 二叉樹的層序遍歷 (opens new window)：通過隊列模擬
求二叉樹的屬性
- 二叉樹：是否對稱 (opens new window)
- 遞歸：後序，比較的是根節點的左子樹與右子樹是不是相互翻轉
- 迭代：使用隊列/棧將兩個節點順序放入容器中進行比較
- 二叉樹：求最大深度 (opens new window)
- 遞歸：後序，求根節點最大高度就是最大深度，通過遞歸函數的返回值做計算樹的高度
- 迭代：層序遍歷
- 二叉樹：求最小深度 (opens new window)
- 遞歸：後序，求根節點最小高度就是最小深度，注意最小深度的定義
- 迭代：層序遍歷
- 二叉樹：求有多少個節點 (opens new window)
- 遞歸：後序，通過遞歸函數的返回值計算節點數量
- 迭代：層序遍歷
- 二叉樹：是否平衡 (opens new window)
- 遞歸：後序，注意後序求高度和前序求深度，遞歸過程判斷高度差
- 迭代：效率很低，不推薦
- 二叉樹：找所有路徑 (opens new window)
- 遞歸：前序，方便讓父節點指向子節點，涉及回溯處理根節點到葉子的所有路徑
- 迭代：一個棧模擬遞歸，一個棧來存放對應的遍歷路徑
- 二叉樹：遞歸中如何隱藏著回溯 (opens new window)
- 詳解二叉樹：找所有路徑 (opens new window)中遞歸如何隱藏著回溯
- 二叉樹：求左葉子之和 (opens new window)
- 遞歸：後序，必須三層約束條件，才能判斷是否是左葉子。
- 迭代：直接模擬後序遍歷
- 二叉樹：求左下角的值 (opens new window)
- 遞歸：順序無所謂，優先左孩子搜索，同時找深度最大的葉子節點。
- 迭代：層序遍歷找最後一行最左邊
- 二叉樹：求路徑總和 (opens new window)
- 遞歸：順序無所謂，遞歸函數返回值為bool類型是為了搜索一條邊，沒有返回值是搜索整棵樹。
- 迭代：棧裡元素不僅要記錄節點指針，還要記錄從頭結點到該節點的路徑數值總和
二叉樹的修改與構造
- 翻轉二叉樹 (opens new window)
- 遞歸：前序，交換左右孩子
- 迭代：直接模擬前序遍歷
- 構造二叉樹 (opens new window)
- 遞歸：前序，重點在於找分割點，分左右區間構造
- 迭代：比較複雜，意義不大
- 構造最大的二叉樹 (opens new window)
- 遞歸：前序，分割點為數組最大值，分左右區間構造
- 迭代：比較複雜，意義不大
- 合併兩個二叉樹 (opens new window)
- 遞歸：前序，同時操作兩個樹的節點，注意合併的規則
- 迭代：使用隊列，類似層序遍歷
求二叉搜索樹的屬性
-
- 遞歸：二叉搜索樹的遞歸是有方向的
- 迭代：因為有方向，所以迭代法很簡單
-
- 遞歸：中序，相當於變成了判斷一個序列是不是遞增的
- 迭代：模擬中序，邏輯相同
求二叉搜索樹的最小絕對差 (opens new window)
- 遞歸：中序，雙指針操作
- 迭代：模擬中序，邏輯相同
-
遞歸：中序，清空結果集的技巧，遍歷一遍便可求眾數集合
遞歸：中序，雙指針操作累加
迭代：模擬中序，邏輯相同
二叉樹公共祖先問題
- 二叉樹的公共祖先問題 (opens new window)
- 遞歸：後序，回溯，找到左子樹出現目標值，右子樹節點目標值的節點。
- 迭代：不適合模擬回溯
- 二叉搜索樹的公共祖先問題 (opens new window)
- 遞歸：順序無所謂，如果節點的數值在目標區間就是最近公共祖先
- 迭代：按序遍歷
二叉搜索樹的修改與構造
- 二叉搜索樹中的插入操作 (opens new window)
- 遞歸：順序無所謂，通過遞歸函數返回值添加節點
- 迭代：按序遍歷，需要記錄插入父節點，這樣才能做插入操作
- 二叉搜索樹中的刪除操作 (opens new window)
- 遞歸：前序，想清楚刪除非葉子節點的情況
- 迭代：有序遍歷，較複雜
- 修剪二叉搜索樹 (opens new window)
- 遞歸：前序，通過遞歸函數返回值刪除節點
- 迭代：有序遍歷，較複雜
- 構造二叉搜索樹 (opens new window)
- 遞歸：前序，數組中間節點分割
- 迭代：較複雜，通過三個隊列來模擬
階段總結
大家以上題目都做過了，也一定要看如下階段小結。
每周小結都會對大家的疑問做統一解答，並且對每周的內容進行拓展和補充，所以一定要看，將細碎知識點一網打盡！
- 本周小結！（二叉樹系列一） (opens new window)
- 本周小結！（二叉樹系列二） (opens new window)
- 本周小結！（二叉樹系列三） (opens new window)
- 本周小結！（二叉樹系列四） (opens new window)
最後總結
在二叉樹題目選擇什麼遍歷順序是不少同學頭疼的事情，我們做了這麼多二叉樹的題目了，Carl給大家大體分分類。
- 涉及到二叉樹的構造，無論普通二叉樹還是二叉搜索樹一定前序，都是先構造中節點。
- 求普通二叉樹的屬性，一般是後序，一般要通過遞歸函數的返回值做計算。
- 求二叉搜索樹的屬性，一定是中序了，要不白瞎了有序性了。
注意在普通二叉樹的屬性中，我用的是一般為後序，例如單純求深度就用前序，二叉樹：找所有路徑 (opens new window)也用了前序，這是為了方便讓父節點指向子節點。
所以求普通二叉樹的屬性還是要具體問題具體分析。
二叉樹專題匯聚為一張圖：
