【完虐算法】樹的基礎遍歷專題

零

LeetCode樹提計劃開始有幾天了。

今天對「樹」的進度做一個簡短的小結，群里親愛的小伙伴進行的怎么樣了呢？我這邊預計在整個「樹」的階段，預計會進行四個小結以及一個完整的復盤，所以，應該是 5 份總結資料。

分布如下：

「樹」的基礎遍歷，重點在于「樹」的遞歸的理解

模塊1：基礎遍歷，對LeetCode中進行刷題標記

模塊2：遍歷變種-自頂向下，對這些題目進行解釋和代碼編寫

模塊3：遍歷變種-非自頂向下，同樣也是對這些題目進行解釋和代碼編寫

最終的復盤總結「最重要」

還是把咱們的計劃列出來：

所以，今天會是先序、中序、后續、層次遍歷的基礎代碼編寫

今天內容相對來說比較容易，就是「樹」的 4 種遍歷。但是，再強調，多看看遞歸的寫法，多深入理解遞歸的代碼流程，因為，可以說這是后面大多數題目的基礎思維邏輯。

后面基本都會使用Python來進行代碼的邏輯實現，比較容易以及大眾，畢竟算法方面學習的是思想，至于怎么實現的，任何語言都可以對其進行復現

今天是「樹」的遍歷，咱們先來定義一個樹的結構類，以及一顆完整的二叉樹！

# 樹結點類 class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None

構建一棵完整的二叉樹：

if __name__ == "__main__": # 新建節點 root = TreeNode('A') node_B = TreeNode('B') node_C = TreeNode('C') node_D = TreeNode('D') node_E = TreeNode('E') node_F = TreeNode('F') node_G = TreeNode('G') node_H = TreeNode('H') node_I = TreeNode('I') # 構建二叉樹 # A # / \ # B C # / \ / \ # D E F G # / \ # H I root.left, root.right = node_B, node_C node_B.left, node_B.right = node_D, node_E node_C.left, node_C.right = node_F, node_G node_D.left, node_D.right = node_H, node_I

首先有一個小提醒：

今天的代碼會使用棧或者隊列來輔助實現，在 Python 中，這里使用 list 來操作

# 棧 stack = [] # 棧 - 壓棧 stack.append('結點') # 棧 - 彈出棧頂元素 stack.pop() # 隊列 queue = [] # 棧 - 入隊 queue.append('結點') # 棧 - 出隊 queue.pop(0)

甜點

很甜，試著深入理解遞歸

遞歸在很多人看來不容易理解，尤其是處于學生時期的同學，以及一些初學者。其實很多工作幾年的人也不是太容易理解遞歸，而且遞歸有時候真的會很不容易解釋，非得自己去想清楚才能真正轉化為自己的一個思維邏輯。

這里我想試著說說看，能不能說清楚，咳、、、盡量吧…

咱們這里用后續遍歷舉例子，其他遞歸方式自己燒腦理解哈！

核心代碼（以下用代碼1、2、3、4來表示每一行）：

def post_order_traverse(root): 代碼1 | if not root: return 代碼2 | post_order_traverse(root.left) 代碼3 | post_order_traverse(root.right) 代碼4 | print(root.value, end=" ")

當執行到圖中步驟 1 的時候，一定是執行了代碼1和代碼2，遞歸調用到最后，判斷結點H左右孩子都為空，執行了 if not root: return，隨后又執行了代碼4，將結點 H 打印了出來。

同理，當執行到圖中的步驟 2 的時候，也是相同的邏輯，遞歸調用，判斷兩個孩子都為空，直接返回，隨后將結點 I 打印了出來。

再往上，結點H 和 結點I 打印并且返回之后，進行回溯，將 結點D 進行打印

依次類推…

（上述描述理解起來還是不太容易，有需要討論的，下面直接加我微信，備注“LeetCode刷題”，我拉群里一起討論哈）

【我的二維碼】

一

先序遍歷

遞歸遍歷過程：

a. 訪問根節點；

b. 先序遍歷其左子樹；

c. 先序遍歷其右子樹；

然后就是一直遞歸下去，在訪問到節點的時候，可以進行節點的相關處理，比如說簡單的訪問節點值

下圖是一棵二叉樹，我們來手動模擬一下遍歷過程

按照上圖中描述，根據順序能夠得到它的一個先序遍歷的過程，得到先序遍歷序列：

A B D H I E C F G

復現上述邏輯：

class Solution: def pre_order_traverse(self, root): if not root: return print(root.value, end=" ") self.pre_order_traverse(root.left) self.pre_order_traverse(root.right)

在整個遞歸中，看似整齊，閱讀性極高的 3 行代碼，其實對于初學者來說，腦子里理解它的的實現流程是比較困難的！

如果不太清晰，建議深入理解上面給到的【甜點】，用心理解，不懂的可以群里直接討論哈！

下面再看看非遞歸的遍歷過程：

a. 訪問根結點。

b. 判斷是否有右孩子，如果有右孩子，壓棧

c. 判斷否則有左孩子，如果有左孩子，訪問它，否則，彈出棧頂元素

d. 循環執行 2 和 3

非遞歸的遍歷，重點在于利用棧來實現將稍后要訪問結點入棧，先遍歷根結點，再將右孩子入棧，最后訪問左孩子這樣的思想

class Solution: def pre_order_traverse_no_recursion(self, root): if not root: return stack = [root] while stack: print(root.value, end=" ") # 訪問根結點 if root.right: stack.append(root.right) # 判斷是否有右孩子，如果有右孩子，壓棧 if root.left: # 判斷否則有左孩子，如果有左孩子，訪問它，否則，彈出棧頂元素 root = root.left else: root = stack.pop()

這種思路其實也是遞歸的變形，將遞歸中使用到的棧自己定義了出來。

二

中序遍歷

咱們還是先來遞歸的實現流程

a. 先序遍歷其左子樹；

b. 訪問根節點；

c. 先序遍歷其右子樹；

然后就是一直遞歸下去，在訪問到節點的時候，可以進行節點的相關處理，比如說簡單的訪問節點值

下圖是一棵二叉樹，我們來手動模擬一下中序遍歷過程

按照上述中序遍歷的遞歸過程，得到中序遍歷序列：

H D I B E A F C G

下面繼續用 Python 來復現上述邏輯：

class Solution: def in_order_traverse(self, root): if not root: return self.in_order_traverse(root.left) print(root.value, end=" ") self.in_order_traverse(root.right)

和先序遍歷很類似，只是把要被訪問結點的 print 語句進行了位置置換。

下面再來看中序遍歷的非遞歸過程：

a. 當遍歷到一個結點時，就壓棧，然后繼續去遍歷它的左子樹;

b. 當左子樹遍歷完成后，從棧頂彈出棧頂元素（左子樹最后一個元素）并訪問它;

c. 最后按照當前指正的右孩子繼續中序遍歷，若沒有右孩子，繼續彈出棧頂元素。

class Solution: def in_order_traverse_no_recursion(self, root): if not root: return stack = [] while stack or root: while root: stack.append(root) root = root.left if stack: tmp = stack.pop() print(tmp.value, end=" ") root = tmp.right

相信上述的 3 個步驟已經說的足夠清楚了，但是還是用更加樸素的語言簡單描述一下：

中序遍歷的非遞歸過程也是利用了一個「棧」來實現，由于是中序遍歷，那么首先要訪問左孩子，進而一定要把每個子結構的根結點入棧，然后訪問左孩子，彈出棧頂元素（訪問根結點），再進行訪問右孩子，訪問右孩子的時候，繼續將每個子結構的根結點入棧，然后訪問左孩子…這樣循環下去，直到棧為空或者指向的根結點為空。

三

后續遍歷

依然先用遞歸來實現

a. 先序遍歷其左子樹；

b. 先序遍歷其右子樹；

c. 訪問根節點；

然后就是一直遞歸下去，在訪問到節點的時候，可以進行節點的相關處理，比如說簡單的訪問節點值

下圖是一棵二叉樹，我們來手動模擬一下后序遍歷過程

按照上述后序遍歷的過程，得到后序遍歷序列：

H I D E B F G C A

咱們用代碼來實現一下邏輯：

class Solution: def post_order_traverse(self, root): if not root: return self.post_order_traverse(root.left) self.post_order_traverse(root.right) print(root.value, end=" ")

依然是很簡潔，依然是將訪問結點的代碼語句的位置進行了調整。

下面來輪到非遞歸來實現的流程

后續遍歷的非遞歸過程比較曲折，后續遍歷需要先訪問左右子結點后，才能訪問該結點，而這也是非遞歸的難點所在。可以使用一個輔助棧來實現，但理解起來沒有使用 2 個棧實現起來清晰，今天就用 2 個棧來實現非遞歸的后續遍歷。

借助2個棧：s1 和 s2

a. 初始化根結點到s1中

b. 將 s1 棧頂元素 T 彈出，到棧 s2 中

c. 判斷 T 是否有左右孩子，如果有依次入棧 s1，否則，執行 b

下面借助圖，還是一樣的樹結構，來梳理一下思路（長圖發放，耐心看完，看完之后會發現思路很清晰）：

有了這個思路就應該會很清晰了，下面就按照這個思維邏輯來編寫代碼：

class Solution: def post_order_traverse_no_recursion1(self, root): s1, s2 = [], [] s1.append(root) # 初始化根結點到S1中 while s1: T = s1.pop() # 將 S1 棧頂元素 T 彈出，到棧 S2 中 s2.append(T) if T.left: # 判斷 T 是否有左右孩子，如果有依次入棧 s1 s1.append(T.left) if T.right: s1.append(T.right) while s2: print(s2.pop().value, end=" ")

看起來 2 個棧像是在忽悠人，其實思路很清晰，代碼很容易就實現了！

四

層次遍歷

層次遍歷屬于 BFS 的范疇，層次遍歷就是按照「樹」的層級進行每一層的掃蕩。

遍歷從根結點開始，首先將根結點入隊，然后開始執行循環：

將頭結點入隊

彈出隊首元素，如果被彈出的隊首元素有左右孩子，將它們依次入隊

循環第 2 直到隊列為空

下面借助一幅圖來描述其遍歷過程：

這樣是不是很清晰，有時候會覺得這種長圖會比動圖好看一些，能清晰看到每一步，而且中間可以有很詳細的解釋。關于圖像展示方面大家可以給出參考意見，這方面確實可以更進一步。

先看代碼吧：

class Solution: def level_order_traverse(self, head): if not head: return queue = [head] while len(queue) > 0: tmp = queue.pop(0) print(tmp.value, end=" ") if tmp.left: queue.append(tmp.left) if tmp.right: queue.append(tmp.right)

今天全部描述完畢！

最后

1.深入理解遞歸，一定一定多思考，咳咳、、我都上了每天上午10點的鬧鈴了（書讀百遍，其義自見）；

2.「樹」的非遞歸遍歷所引導的思維方式很重要；

3.下期進行【基礎遍歷】中LeetCode題目羅列以及利用樹遞歸的方式，會產生一些計算樹相關的變形問題

代碼和本文的文檔都在 https://github.com/xiaozhutec/share_leetcode , 需要的小伙伴可以自行下載代碼運行跑起來！有空可以幫我點點 star。謝過大家！

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。