綱領

1.是否可以通過遍歷一遍二叉樹得到答案

2.是否可以通過兩顆子樹相同問題的答案推導出樹的答案(形式為遞歸)

無論哪種思維模式，都需要思考:單獨一個二叉樹節(jié)點，它需要做什么事情？需要在什么時候做

后序

判斷問題是否和子樹相關，如果相關，就要給函數(shù)設置合理的定義和返回值，在后序位置寫代碼。

子樹相同問題 推導

子樹不同問題 遍歷

紅黑樹應用場景限制

紅黑樹(自平衡BST(自平衡(由n個節(jié)點構建子樹,保證子樹高度相差<=1(Δ(h(sub)<=1便可保證整樹是最小高度(因為整樹高度=子樹高度+1))))))
RBT作為數(shù)據(jù)結構，其增刪改查可謂達到了完美，但即便如此，其應用場景也有限制。請說出合適的場景。

構造對比

1008

105

什么是二叉樹遍歷

二叉樹遍歷 = 前中后序遍歷
= 遞歸遍歷 + 3種時間節(jié)點
遞歸遍歷會依次遍歷到每個節(jié)點。
而前中后序則是在遞歸遍歷的基礎上選擇操作發(fā)生的時間。

遞歸遍歷

遞歸遍歷的順序是固定的。也就是每個節(jié)點的遍歷順序是固定的。
沒錯，也許你會認為是有三種遍歷順序，但其實只有一種，只決定于遞歸。

1.前序遍歷 = 進入節(jié)點時

2.中序遍歷 = 遍歷完左子樹回到節(jié)點。此操作需要等到所有左樹節(jié)點做完后才會做

3.后序遍歷 = 遍歷完左右子樹回到節(jié)點。左右子樹的所有節(jié)點都做完操作后，回到當前節(jié)點才會做此操作 = 離開節(jié)點

遍歷要點

1.每個節(jié)點做什么

2.在什么時間做

節(jié)點時機的區(qū)別

897. 遞增順序搜索樹

144. 二叉樹的前序遍歷

226. 翻轉二叉樹

待做

13 106. 從中序與后序遍歷序列構造二叉樹*

15 331. 驗證二叉樹的前序序列化*

為什么不能優(yōu)化

572. 另一棵樹的子樹

1367. 二叉樹中的列表

遍歷推導，不能優(yōu)化

推導是一類特殊關系

指樹的問題可以由子樹同樣的問題推導而來

推導公式

二叉樹分解算法的核心思維是樹間的推導
1.f(x) == f(x) + 1;