[二叉樹的面試演算法]（八）之二叉樹演算法解題思路總結(26題)

在前面七篇關於二叉樹的文章中，列舉了二叉樹常見的七種題型。在解題的過程中，發現用遞迴，迭代和新增臨時變數記錄中間資訊這三種方法，是常見的套路。接下來，對前文中，二叉樹出現的所有題目，按照這三種解題方法來分類，進行彙總。

1。遞迴方式

1.1 基本遞迴

1。 線上OJ練習地址：二叉樹的前序遍歷

2。 線上OJ練習地址：二叉樹的中序遍歷

3。 線上OJ練習地址：二叉樹的後序遍歷

三種基本的遍歷方式，都可以用遞迴來實現。寫遞迴演算法的時候，需要注意遞迴退出條件以及遞迴操作的表達。

4。 二叉樹的節點個數 - leetcode222

5。 二叉搜尋樹的最近公共祖先-Leetcode235

6。 二叉樹的最近公共祖先-leetcode236

在

二叉樹節點的個數

中，

該題的遞迴的思想為

：當root為空時，返回0，否則，返回左子樹的節點數+右子樹的節點數+1；在

求二叉搜尋樹的最近公共祖先

中，根據二叉搜尋樹的特性，若節點小於根節點，則在根節點的左子樹中，若大於根節點，則在根節點的右子樹中。所以，

該題的遞迴思路是

：若節點p，q均小於根節點，則返回左子樹的最低公共祖先。若兩者均大於根節點，則返回右子樹的最低公共祖先，否則，最低公共祖先即為當前根節點。同理，在

求二叉樹的最近公共祖先

中，先查詢p，q是否在左子樹中，結果記錄為left，再查詢p，q是否在右子樹中，結果記錄為right；若p，q不都在左子樹或者右子樹中，則當前root的節點為最近公共祖先，否則，left，right中不為空的為最近公共祖先。

7。 二叉樹的最大深度-leetcode104

8。 二叉樹的最小深度 -leetcode111

求

二叉樹的最大深度

，即若根節點為空，返會0，否則返回左右子樹中高度較大者+1。求

二叉樹的最小深度

，若根節點為空，返回0，若左右孩子均為非空，返回較小的子樹的高度+1，否則，返回非空子樹的高度+1；

1.2 基本遞迴 + 臨時變數

09。 二叉樹的所有路徑-leetcode257

10。 二叉樹中和為某一值的路徑_牛客網

11。 二叉樹的直徑_leetcode545

求二叉樹的所有路徑

，即先序遍歷二叉樹。當到達葉子節點時，將路徑儲存到結果集中。在這個過程中，需要新建path臨時變數，存放路徑的資訊；在

求二叉樹的和為某一值的路徑

中，依舊是先序遍歷二叉樹，在到達葉子節點是，比較路徑的和，是否與target相等，若相等則儲存路徑，否則不儲存。在

求二叉樹的直徑一題

中，在求二叉樹的高度的過程中，透過一個變數來記錄二叉樹中直徑的最大值。

12。 判斷兩棵二叉樹是否相同_leetcode100

13。 判斷一棵樹是否是平衡二叉樹_leetcode110

14。 翻轉二叉樹_leetcode226

15。 判斷一棵樹是否為對稱二叉樹_leetcode101

在判斷樹的結構中，遞迴是最好的方法。

判斷兩棵二叉樹是否相同

，只要判斷根節點相同，且root1的左孩子與root2的左孩子相同且root1的右孩子與root2的右孩子結構相同；同理，

判斷是否為平衡二叉樹中

，要求root左孩子高度與右孩子高度只差不超過1，且左右孩均為平衡二叉樹。在

翻轉二叉樹

中，先將當前節點的左孩子和右孩子交換。然後分別對左子樹和右子樹遞迴進行翻轉操作；

在判斷對稱二叉樹中

，可轉換為，遞迴判斷左子樹和右子樹的結構一樣。

16。 從前序與中序遍歷序列構造二叉樹_leetcode105

17。 從中序與後序遍歷序列構造二叉樹_leetcode106

18。 根據前序和後序遍歷構造二叉樹_leetcode889

在重構二叉樹中，主要也是用到了遞迴演算法。根據前序/後續遍歷確定根節點，然後結合中序遍歷，確定左子樹和右子樹對應的前序/中序序列，遞迴構造。

2。迭代方式

2.1 棧+臨時變數+迭代

19。 二叉樹的後序遍歷經典非遞迴版

20。 二叉搜尋樹中第K小的元素-leetcode230

21。 二叉樹的下一個結點_牛客網

在

二叉樹的後序遍歷經典非遞迴版

一文中，後序遍歷的非遞迴實現，使用的是棧+臨時變數prev，curr分別記錄前一個訪問節點和當前訪問節點，來實現非遞迴遍歷。

求二叉搜尋樹的第K小元素

中，新增一個計數器+棧實現中序遍歷，實現對第K個元素的跟蹤。在求

二叉樹中的中序遍歷下一個節點中，

該題目的樹節點多了一個指標，來實現對父節點的記錄，從而可以結合棧來實現輸出下一個節點。

22。 二叉樹的鋸齒形層次遍歷_leetcode103

二叉樹的鋸齒形層次遍歷中，使用兩個棧，分別存放奇數層和偶數層的節點。

2.2佇列+臨時變數+迭代

23。 二叉樹的層次遍歷

24。 自下而上分層遍歷_leetcode107

25。列印二叉樹第K層節點（小米一面筆試題）

層次遍歷

，使用佇列存放每一層節點，一個臨時變數len，記錄每一層的節點個數。

自下而上的分層遍歷中

，在層次遍歷的基礎上，將每一層的結果插入結果集的最前面，即可實現。列印第K層節點，新增一個計數器，來記錄節點的層數。

26。 二叉樹的序列化與反序列化_leetcode297

在二叉樹的序列化和反序列化一題中，主要是結合來處理字串一起處理。透過特殊字元來記錄空指標資訊。可以很方便的重構出二叉樹。