【演算法】二叉樹遍歷演算法總結：前序中序後序遍歷

前言

二叉樹遍歷是非常經典的演算法題，也是二叉樹的一道基礎演算法題。

但是在平常的筆試面試中，其出現的頻率其實並不是特別的高，我推測是這種題目相對來說比較基礎，算是一個基礎知識點。

比如劍指offer中出現的後序遍歷題目，是給出一個數字序列，讓你判斷是不是平衡二叉樹後序遍歷序列，這樣出題的難度比直接讓你寫後序遍歷難很多。

但是，二叉樹遍歷容易嗎？在遞迴方法下，前中後序遍歷都是一個思路，理解起來也比較容易。

但是隻是用迭代的話，二叉樹遍歷其實是有難度的！

，這也是為什麼LeetCode會在這三題題目的下方寫出

進階： 遞迴演算法很簡單，你可以透過迭代演算法完成嗎？

這句話了。

本文的主要內容如下：

題目定義

：

上篇：二叉樹前序、中序、後序遍歷

下篇：層序遍歷、其他遍歷相關題型

解題思路

：遞迴 + 迭代+

莫里斯Morris遍歷

解題程式碼

：Java + Python

注1

：本文中的解題思路會盡量的全面，但是解題方法千變萬化，有很多奇技淫巧我不會去介紹，大家有興趣可以自行擴充套件學習。

注2

：本文中的程式碼會盡量簡單，易懂，並不會去追求極致的寫法（比如：在一行內完成，使用各種非正式的庫等）。

正文

二叉樹的定義

最多有兩棵子樹的樹被稱為二叉樹

二叉樹下還有很多種特殊的二叉樹，下方簡單介紹幾種常用的。

滿二叉樹

二叉樹中所有非葉子結點的度都是2，且葉子結點都在同一層次上

完全二叉樹（可以不滿）

如果一個二叉樹與滿二叉樹前m個節點的結構相同，這樣的二叉樹被稱為完全二叉樹。也就是說，如果把滿二叉樹從右至左、從下往上刪除一些節點，剩餘的結構就構成完全二叉樹。

二叉搜尋樹

二叉查詢樹（BinarySearch Tree，也叫二叉搜尋樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或者是具有下列性質的二叉樹：

若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；

若它的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；

它的左、右子樹也分別為二叉排序樹

二叉樹前中後序遍歷

遍歷方法

前序遍歷：根結點 ——-> 左子樹 ——-> 右子樹

中序遍歷：左子樹——-> 根結點 ——-> 右子樹

後序遍歷：左子樹 ——-> 右子樹 ——-> 根結點

題目介紹

前序遍歷

LeetCode題目地址：

https：//

leetcode-cn。com/problem

s/binary-tree-preorder-traversal/

輸入： ［1，null，2，3］

1

\

2

/

3

輸出： ［1，2，3］

中序遍歷

LeetCode題目地址：

https：//

leetcode-cn。com/problem

s/binary-tree-inorder-traversal/

輸入： ［1，null，2，3］

1

\

2

/

3

輸出： ［1，3，2］

後序遍歷

LeetCode題目地址：

https：//

leetcode-cn。com/problem

s/binary-tree-postorder-traversal/

輸入： ［1，null，2，3］

1

\

2

/

3

輸出： ［3，2，1］

解題思路詳解與程式碼實現

二叉樹的前中後序遍歷，主要就是兩種思路，一種是遞迴，一種是迭代。

如果看到這裡還沒有感覺，不用擔心，先直接往下看，第一個程式碼（前序遍歷的遞迴思路）會幫助你提升感覺。

遞迴思路

遞迴思路是最容易理解的思路，並且前中後序遍歷都相同。

比如前序遍歷，在遞迴的函數里，先往結果數組裡加入根節點，然後加入根節點的左節點，然後加入根節點的右節點。最後所有遞迴的函式執行完畢，結果集就已經完成了。

中序和後序的思路相同，就不再贅述了。

前序遍歷

Java：

class Solution {

public List preorderTraversal（TreeNode root） {

List result = new ArrayList<>（）；

if （root == null） {

return result；

}

preorder（root， result）；

return result；

}

private static List preorder（TreeNode root， List result） {

if （root ！= null） {

result。add（root。val）；

preorder（root。left， result）；

preorder（root。right， result）；

}

return result；

}

}

Python：

class Solution（object）：

def _preorderTraversal（self， root， result）：

if root：

result。append（root。val）

self。_preorderTraversal（root。left， result）

self。_preorderTraversal（root。right， result）

def preorderTraversal（self， root）：

“”“

：type root： TreeNode

：rtype： List［int］

”“”

if root == None：

return ［］

result = ［］

self。_preorderTraversal（root， result）

return result

中序遍歷

Java：

class Solution {

public List inorderTraversal（TreeNode root） {

List result = new ArrayList<>（）；

if （root == null） {

return result；

}

result = inorder（root， result）；

return result；

}

private static List inorder（TreeNode root， List result） {

if （root ！= null） {

inorder（root。left， result）；

result。add（root。val）；

inorder（root。right， result）；

}

return result；

}

}

Python：

class Solution（object）：

def generate（self， root， result）：

if root：

self。inorder（root。left， list）

result。append（root。val）

self。inorder（root。right， list）

def inorderTraversal（self， root）：

“”“

：type root： TreeNode

：rtype： List［int］

”“”

if not root：

return ［］

result = ［］

self。generate（root， result）

return result

後序遍歷

Java：

class Solution {

public List postorderTraversal（TreeNode root） {

List result = new ArrayList<>（）；

if （root == null） {

return result；

}

result = postorder（root， result）；

return result；

}

private static List postorder（TreeNode root， List result） {

if （root ！= null） {

postorder（root。left， result）；

postorder（root。right， result）；

result。add（root。val）；

}

return result；

}

}

Python：

class Solution（object）：

def _postorderTraversal（self， root， result）：

if root：

self。_postorderTraversal（root。left， result）

self。_postorderTraversal（root。right， result）

result。append（root。val）

def postorderTraversal（self， root）：

“”“

：type root： TreeNode

：rtype： List［int］

”“”

if root == None：

return ［］

result = ［］

self。_postorderTraversal（root， result）

return result

迭代思路

前序遍歷

我們需要一個棧來完成遍歷。

1。根節點入棧

2。取出節點，值加入結果，然後先加右，後加左。

3。重複2

這樣就得到了 根節點——左子樹——右子樹 的遍歷結果集。

Java：

來自官方題解

LinkedList stack = new LinkedList<>（）；

LinkedList output = new LinkedList<>（）；

if （root == null） {

return output；

}

stack。add（root）；

while （！stack。isEmpty（）） {

TreeNode node = stack。pollLast（）；

output。add（node。val）；

if （node。right ！= null） {

stack。add（node。right）；

}

if （node。left ！= null） {

stack。add（node。left）；

}

}

return output；

}

Python：

class Solution（object）：

def preorderTraversal（self， root）：

“”“

：type root： TreeNode

：rtype： List［int］

”“”

ret = ［］

stack = ［root］

while stack：

node = stack。pop（）

if node：

ret。append（node。val）

if node。right：

stack。append（node。right）

if node。left：

stack。append（node。left）

return ret

中序遍歷

還是使用一個棧來解決問題。

步驟如下：

1

/ \

2 3

/ \ / \

4 5 6 7

我們將根節點1入棧，如果有左孩子，依次入棧，那麼入棧順序為：1，2，4。由於4的左子樹為空，停止入棧，此時棧為{1，2，4}。

此時將4出棧，並遍歷4，由於4也沒有右孩子，那麼根據中序遍歷的規則，我們顯然應該繼續遍歷4的父親2，情況是這樣。所以我們繼續將2出棧並遍歷2，2存在右孩子，將5入棧，此時棧為{1，5}。

5沒有孩子，則將5出棧並遍歷5，這也符合中序遍歷的規則。此時棧為{1}。

1有右孩子，則將1出棧並遍歷1，然後將右孩子3入棧，並繼續以上三個步驟即可。

棧的變化過程：{1}->{1，2}->{1，2，4}->{1，2}->{1}->{1，5}->{1}->{}->{3}->{3，6}->{3}->{}->{7}->{}。

總結：從根節點遍歷，先放入所有有左孩子的節點直到沒有，然後出棧，出棧的時候就將出棧的數字放入結果集，然後看其有沒有右孩子，有的話右孩子入棧。

Java：

官方題解

public class Solution {

public List inorderTraversal（TreeNode root） {

List res = new ArrayList<>（）；

Stack stack = new Stack<>（）；

TreeNode curr = root；

while （curr ！= null || ！stack。isEmpty（）） {

while （curr ！= null） {

stack。push（curr）；

curr = curr。left；

}

curr = stack。pop（）；

res。add（curr。val）；

curr = curr。right；

}

return res；

}

}

Python：

class Solution：

# @param root， a tree node

# @return a list of integers

def inorderTraversal（self， root）：

result = ［］

stack = ［］

while root or stack：

if root：

stack。append（root）

root = root。left

else：

root = stack。pop（）

result。append（root。val）

root = root。right

return result

後序遍歷

將陣列輸出為右子樹-左子樹-根節點。

最後，再將陣列倒序輸出

，形成後序遍歷。這樣程式碼並不用很繁瑣，也能做完迭代。

是不是似曾相識，沒錯，

和前序遍歷的迭代幾乎一樣

，僅僅是先放右節點再放左節點變成了先放左節點再放右節點，然後倒序輸出。

Java：

class Solution {

public List postorderTraversal（TreeNode root） {

LinkedList stack = new LinkedList<>（）；

LinkedList output = new LinkedList<>（）；

if （root == null） {

return output；

}

stack。add（root）；

while （！stack。isEmpty（）） {

TreeNode node = stack。pollLast（）；

output。addFirst（node。val）；

if （node。left ！= null） {

stack。add（node。left）；

}

if （node。right ！= null） {

stack。add（node。right）；

}

}

return output；

}

}

Python：

class Solution（object）：

def postorderTraversal（self， root）：

“”“

：type root： TreeNode

：rtype： List［int］

”“”

if root is None：

return ［］

ret = ［］

stack = ［root］

while stack：

node = stack。pop（）

if node：

ret。append（node。val）

if node。left：

stack。append（node。left）

if node。right：

stack。append（node。right）

return ret［：：-1］

所以迭代方式，前後序是非常類似的，中序遍歷可能需要單獨理解下。

莫里斯遍歷

二叉樹常規的遍歷方法是用遞迴來實現的，這種方法一般都需要O（n）的空間複雜度和O（n）的時間複雜度。而Morris方法實現的是O（1）的空間複雜度和O（n）的時間複雜度。

我們知道，遍歷二叉樹時，最大的難點在於，遍歷到子節點的時候怎樣重新返回到父節點（假設節點中沒有指向父節點的p指標），由於不能用棧作為輔助空間。（不然就是普通迭代方法）。

為了解決這個問題，Morris方法用到了

線索二叉樹

（threaded binary tree）的概念。在Morris方法中不需要為每個節點額外分配指標指向其前驅（predecessor）和後繼節點（successor），只需要利用葉子節點中的

左右空指標指向某種順序遍歷下的前驅節點或後繼節點就可以了

。

聽不懂沒關係，下面使用中序遍歷作為例子來理解莫里斯遍歷到底是什麼意思，例子來自LeetCode官方題解：

中序遍歷

Step 1： 將當前節點current初始化為根節點

Step 2： While current不為空，

若current沒有左子節點

a。 將current新增到輸出

b。 進入右子樹，亦即， current = current。right

否則

a。 在current的左子樹中，令current成為最右側節點的右子節點

b。 進入左子樹，亦即，current = current。left

1

/ \

2 3

/ \ /

4 5 6

首先，1 是根節點，所以將 current 初始化為 1。1 有左子節點 2，current 的左子樹是

2

/ \

4 5

在此左子樹中最右側的節點是 5，於是將 current（1） 作為 5 的右子節點。令 current = cuurent。left （current = 2）。 現在二叉樹的形狀為：

2

/ \

4 5

\

1

\

3

/

6

對於 current（2），其左子節點為4，我們可以繼續上述過程

4

\

2

\

5

\

1

\

3

/

6

Java：

class Solution {

public List < Integer > inorderTraversal（TreeNode root） {

List < Integer > res = new ArrayList < > （）；

TreeNode curr = root；

TreeNode pre；

while （curr ！= null） {

if （curr。left == null） {

res。add（curr。val）；

curr = curr。right； // move to next right node

} else { // has a left subtree

pre = curr。left；

while （pre。right ！= null） { // find rightmost

pre = pre。right；

}

pre。right = curr； // put cur after the pre node

TreeNode temp = curr； // store cur node

curr = curr。left； // move cur to the top of the new tree

temp。left = null； // original cur left be null， avoid infinite loops

}

}

return res；

}

}

前序遍歷

理解了中序遍歷，前序和後序遍歷相對來說也就更容易理解了。所以前序和後序貼了思路，程式碼我也沒自己寫後submit，在這裡就不放了。

演算法的思路是從當前節點向下訪問先序遍歷的前驅節點，每個前驅節點都恰好被訪問兩次。

首先從當前節點開始，向左孩子走一步然後沿著右孩子一直向下訪問，直到到達一個葉子節點（當前節點的中序遍歷前驅節點），所以我們更新輸出並建立一條偽邊 predecessor。right = root 更新這個前驅的下一個點。如果我們第二次訪問到前驅節點，由於已經指向了當前節點，我們移除偽邊並移動到下一個頂點。

後序遍歷

後續遍歷稍顯複雜，需要建立一個臨時節點dump，令其左孩子是root。並且還需要一個子過程，就是倒序輸出某兩個節點之間路徑上的各個節點。

步驟：

當前節點設定為臨時節點dump。

如果當前節點的左孩子為空，則將其右孩子作為當前節點。

如果當前節點的左孩子不為空，在當前節點的左子樹中找到當前節點在中序遍歷下的前驅節點。

a） 如果前驅節點的右孩子為空，將它的右孩子設定為當前節點。當前節點更新為當前節點的左孩子。

b） 如果前驅節點的右孩子為當前節點，將它的右孩子重新設為空。倒序輸出從當前節點的左孩子到該前驅節點這條路徑上的所有節點。當前節點更新為當前節點的右孩子。

重複以上1、2直到當前節點為空。

參考

https：//

leetcode-cn。com/problem

s/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/

https：//www。

cnblogs。com/AnnieKim/ar

chive/2013/06/15/morristraversal。html

https：//

blog。csdn。net/softwarex

4/article/details/95986102

關注我

我是一名後端開發工程師。

主要關注後端開發，資料安全，爬蟲，物聯網，邊緣計算等方向，歡迎交流。

各大平臺都可以找到我

微信公眾號：後端技術漫談

Github：@qqxx6661

CSDN：@Rude3knife

知乎：@後端技術漫談

簡書：@蠻三刀把刀

掘金：@蠻三刀把刀

原創部落格主要內容

後端開發相關技術文章

Java面試知識點複習全手冊

設計模式/資料結構

LeetCode/劍指offer 演算法題解析

SpringBoot/SpringCloud菜鳥入門實戰系列

爬蟲相關技術文章

逸聞趣事/好書分享/個人生活

個人公眾號：後端技術漫談

如果文章對你有幫助，不妨收藏，投幣，轉發，在看起來~