前言
之前小六六一直覺得自己的算法比較菜，算是一個短闆吧，以前刷題也還真是三天打魚，兩天曬網，刷幾天，然後就慢慢的不堅持了，是以這次，借助平台的活動，打算慢慢的開始開刷，并且自己還會給刷的題總結下，談談自己的一些思考，和自己的思路等等，希望對小夥伴能有所幫助吧，也可以借此機會把自己短闆補一補，希望自己能堅持下去呀
連結清單的合集
- 六六力扣刷題哈希表之哈希理論
- 六六力扣刷題哈希表之有效的字母異位詞
- 六六力扣刷題哈希表之兩個數組的交集
- 六六力扣刷題哈希表之快樂數
- 六六力扣刷題哈希表之贖金信
- 六六力扣刷題哈希表之三數之和
字元串
- 六六力扣刷題字元串之反轉字元串
- 六六力扣刷題字元串之反轉字元串2
- 六六力扣刷題字元串之替換空格
- 六六力扣刷題字元串之反轉字元串中的單詞
- 六六力扣刷題字元串之找出字元串中第一個比對項的下
- 六六力扣刷題字元串之重複的子字元串
雙指針
- 六六力扣刷題雙指針之移除元素
- 六六力扣刷題雙指針之删除連結清單的倒數第N個節點
- 六六力扣刷題雙指針之連結清單相交
- 六六力扣刷題雙指針之三數之和
- 六六力扣刷題雙指針之反轉連結清單
二叉樹
二叉樹是我們經常會用到的一種資料結構，在我們日常刷題和程式設計中都有很大的用處，本篇講一下我所了解的二叉樹的相關知識。
二叉樹的種類
- 滿二叉樹
- 完全二叉樹
滿二叉樹
滿二叉樹：如果一棵二叉樹隻有度為0的結點和度為2的結點，并且度為0的結點在同一層上，則這棵二叉樹為滿二叉樹。
這棵二叉樹為滿二叉樹，也可以說深度為k，有2^k-1個節點的二叉樹。
完全二叉樹
什麼是完全二叉樹？
完全二叉樹的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其餘每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若幹位置。若最底層為第 h 層，則該層包含 1~ 2^h -1 個節點。
大家要自己看完全二叉樹的定義，很多同學對完全二叉樹其實不是真正的懂了。
我來舉一個典型的例子如題：
二叉搜尋樹
前面介紹的樹，都沒有數值的，而二叉搜尋樹是有數值的了，二叉搜尋樹是一個有序樹。
- 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
- 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
- 它的左、右子樹也分别為二叉排序樹
下面這兩棵樹都是搜尋樹
平衡二叉搜尋樹：又被稱為AVL（Adelson-Velsky and Landis）樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
如圖：
最後一棵 不是平衡二叉樹，因為它的左右兩個子樹的高度差的絕對值超過了1。
C++中map、set、multimap，multiset的底層實作都是平衡二叉搜尋樹，是以map、set的增删操作時間時間複雜度是logn，注意我這裡沒有說unordered_map、unordered_set，unordered_map、unordered_map底層實作是哈希表。
是以大家使用自己熟悉的程式設計語言寫算法，一定要知道常用的容器底層都是如何實作的，最基本的就是map、set等等，否則自己寫的代碼，自己對其性能分析都分析不清楚！
二叉樹的存儲方式
二叉樹可以鍊式存儲，也可以順序存儲。
那麼鍊式存儲方式就用指針， 順序存儲的方式就是用數組。
顧名思義就是順序存儲的元素在記憶體是連續分布的，而鍊式存儲則是通過指針把分布在散落在各個位址的節點串聯一起。
二叉樹的周遊方式
關于二叉樹的周遊方式，要知道二叉樹周遊的基本方式都有哪些。
一些同學用做了很多二叉樹的題目了，可能知道前中後序周遊，可能知道層序周遊，但是卻沒有架構。
我這裡把二叉樹的幾種周遊方式列出來，大家就可以一一串起來了。
二叉樹主要有兩種周遊方式：
- 深度優先周遊：先往深走，遇到葉子節點再往回走。
- 廣度優先周遊：一層一層的去周遊。
這兩種周遊是圖論中最基本的兩種周遊方式，後面在介紹圖論的時候 還會介紹到。
那麼從深度優先周遊和廣度優先周遊進一步拓展，才有如下周遊方式：
- 深度優先周遊
- 前序周遊（遞歸法，疊代法）
- 中序周遊（遞歸法，疊代法）
- 後序周遊（遞歸法，疊代法）
- 廣度優先周遊
- 層次周遊（疊代法）
在深度優先周遊中：有三個順序，前中後序周遊， 有同學總分不清這三個順序，經常搞混，我這裡教大家一個技巧。
這裡前中後，其實指的就是中間節點的周遊順序，隻要大家記住 前中後序指的就是中間節點的位置就可以了。
看如下中間節點的順序，就可以發現，中間節點的順序就是所謂的周遊方式
- 前序周遊：中左右
- 中序周遊：左中右
- 後序周遊：左右中
大家可以對着如下圖，看看自己了解的前後中序有沒有問題。
最後再說一說二叉樹中深度優先和廣度優先周遊實作方式，我們做二叉樹相關題目，經常會使用遞歸的方式來實作深度優先周遊，也就是實作前中後序周遊，使用遞歸是比較友善的。
之前我們講棧與隊列的時候，就說過棧其實就是遞歸的一種是實作結構，也就說前中後序周遊的邏輯其實都是可以借助棧使用非遞歸的方式來實作的。
而廣度優先周遊的實作一般使用隊列來實作，這也是隊列先進先出的特點所決定的，因為需要先進先出的結構，才能一層一層的來周遊二叉樹。
這裡其實我們又了解了棧與隊列的一個應用場景了。
具體的實作我們後面都會講的，這裡大家先要清楚這些理論基礎。
結束
二叉樹是一種基礎資料結構，在算法面試中都是常客，也是衆多資料結構的基石。