一文弄懂二叉樹三種遍歷

作者 | 菠了個菜

二叉樹的遍歷是指從根結點出發，按照某種次序依次訪問二叉樹中所有結點，使得每個結點被訪問一次且僅被訪問一次。

在二叉樹的遍歷中存在三種較為常用的遍歷方式：前序遍歷、中序遍歷、後序遍歷。本文筆者將嘗試著以圖文結合的方式向讀者詳細的介紹這三種遍歷方式的邏輯思路，希望讓讀者看到任何的二叉樹都能在腦海中快速的勾勒出動畫。

前提

在介紹這三組動畫前，我們先用圖來介紹一下二叉樹的創建以及動畫中的一些約定說明。

如圖所示是二叉樹中的一個節點，這個節點有左子樹與右子樹，通過兩根綠色的連接線，將此節點劃分成了三個區域，我們分別用前、中、後這三個輔助點來表示。

這三個點表明在二叉樹的遍歷中什麼時候要取出此節點的值。

任何一個節點去遍歷都是：前-左綠線-中-右綠線-後，這樣的順序遍歷的。

前序遍歷

使用遞歸方式實現前序遍歷的具體過程為：

• 先訪問根節點
• 再序遍歷左子樹
• 最後序遍歷右子樹

我們來對上圖進行一個充分的說明來理解前序遍歷的遞歸實現方式。

• 首先訪問了28這個節點，我們看前輔助點，由於是前序遍歷，那麼此刻我們取出該節點的值28
• 而後通過左綠線訪問28的左子樹
• 在16這個節點中，我們看前輔助點，由於是前序遍歷，取出該節點的值16
• 通過左綠線訪問16的左子樹
• 在13這個節點中，我們看前輔助點，由於是前序遍歷，取出該節點的值13
• 13這個節點左子樹為空，那麼我們左綠線就沒有，然後看中輔助點，由於是前序遍歷，因此不做處理
• 13這個節點右子樹為空，那麼我們右綠線就沒有，然後看後輔助點，由於是前序遍歷，因此不做處理
• 而後回到16這個節點中，看中輔助點，由於是前序遍歷，因此不做處理
• 而後看16這個節點的右子樹22這個節點，看前輔助點，由於是前序遍歷，取出該節點的值22

代碼實現：

/// 144. Binary Tree Preorder Traversal
/// https://leetcode.com/problems/binary-tree-preorder-traversal/description/
/// 二叉樹的前序遍歷
/// 時間複雜度: O(n), n為樹的節點個數
/// 空間複雜度: O(h), h為樹的高度
class Solution {
public:
 vector preorderTraversal(TreeNode* root) {
 vector res;
 __preorderTraversal(root, res);
 return res;
 }
private:
 void __preorderTraversal(TreeNode* node, vector &res){
 if(node){
 res.push_back(node->val);
 __preorderTraversal(node->left, res);
 __preorderTraversal(node->right, res);
 }
 }
};

中序遍歷

使用遞歸方式實現中序遍歷的具體過程為：

• 先中序遍歷左子樹
• 再訪問根節點
• 最後中序遍歷右子樹

我們來對上圖進行一個充分的說明來理解中序遍歷的遞歸實現方式。

• 首先訪問了28這個節點，我們看前輔助點，由於是中序遍歷，因此不做處理
• 而後通過左綠線訪問28的左子樹
• 在16這個節點中，我們看前輔助點，由於是中序遍歷，因此不做處理
• 通過左綠線訪問16的左子樹
• 在13這個節點中，我們看前輔助點，由於是中序遍歷，因此不做處理
• 13這個節點左子樹為空，那麼我們左綠線就沒有，然後看中輔助點，由於是中序遍歷，取出該節點的值13
• 13這個節點右子樹為空，那麼我們右綠線就沒有，然後看後輔助點，由於是中序遍歷，因此不做處理
• 而後回到16這個節點中，看中輔助點，由於是中序遍歷，取出該節點的值16
• 而後看16這個節點的右子樹22這個節點，看前輔助點，由於是中序遍歷，因此不做處理
• 看中輔助點，由於是中序遍歷，取出該節點的值22

代碼實現：

/// 94. Binary Tree Inorder Traversal
/// https://leetcode.com/problems/binary-tree-inorder-traversal/solution/
/// 二叉樹的中序遍歷
/// 時間複雜度: O(n), n為樹的節點個數 

/// 空間複雜度: O(h), h為樹的高度
class Solution {
public:
 vector inorderTraversal(TreeNode* root) {
 vector res;
 __inorderTraversal(root, res);
 return res;
 }
private:
 void __inorderTraversal(TreeNode* node, vector &res){
 if( node ){
 __inorderTraversal(node->left, res);
 res.push_back( node->val );
 __inorderTraversal(node->right, res);
 }
 }
};

後序遍歷

使用遞歸方式實現後序遍歷的具體過程為：

• 先後序遍歷左子樹
• 再後序遍歷右子樹
• 最後訪問根節點

我們來對上圖進行一個充分的說明來理解後序遍歷的遞歸實現方式。

• 首先訪問了28這個節點，我們看前輔助點，由於是後序遍歷，因此不做處理
• 而後通過左綠線訪問28的左子樹
• 在16這個節點中，我們看前輔助點，由於是後序遍歷，因此不做處理
• 通過左綠線訪問16的左子樹
• 在13這個節點中，我們看前輔助點，由於是後序遍歷，因此不做處理
• 13這個節點左子樹為空，那麼我們左綠線就沒有，然後看中輔助點，由於是後序遍歷，因此不做處理
• 13這個節點右子樹為空，那麼我們右綠線就沒有，然後看後輔助點，由於是後序遍歷，取出該節點的值13
• 而後回到16這個節點中，看中輔助點，由於是後序遍歷，因此不做處理
• 而後看16這個節點的右子樹22這個節點，看前輔助點，由於是中序遍歷，因此不做處理
• 看中輔助點，由於是後序遍歷，因此不做處理
• 看後輔助點，由於是後序遍歷，取出該節點的值16

代碼實現：

/// 145. Binary Tree Postorder Traversal
/// https://leetcode.com/problems/binary-tree-postorder-traversal/description/
/// 二叉樹的後序遍歷
/// 時間複雜度: O(n), n為樹的節點個數
/// 空間複雜度: O(h), h為樹的高度
class Solution {
public:
 vector postorderTraversal(TreeNode* root) {
 vector res;
 __postorderTraversal(root, res);
 return res;
 }
private:
 void __postorderTraversal(TreeNode* node, vector &res){
 if( node ){
 __postorderTraversal(node->left, res);
 __postorderTraversal(node->right, res);
 res.push_back(node->val);
 }
 }
};

作者簡介：菠了個菜，本文首發於個人公眾號「五分鐘學算法」。「五分鐘學算法」是致力於通過各種動畫的形式來描繪出各種數據結構，並圖解 LeetCode 原題的學習平臺。

閱讀更多 CSDN 的文章

關鍵字: 計算複雜性理論 結點 遍歷