二叉樹的遍歷是指從根結點出發(fā)，按照某種次序依次訪問二叉樹中所有結點，使得每個結點被訪問一次且僅被訪問一次。
在二叉樹的遍歷中存在三種較為常用的遍歷方式：前序遍歷、中序遍歷、后序遍歷。本文筆者將嘗試著以圖文結合的方式向讀者詳細的介紹這三種遍歷方式的邏輯思路，希望讓讀者看到任何的二叉樹都能在腦海中快速的勾勒出動畫。
前提
在介紹這三組動畫前，我們先用圖來介紹一下二叉樹的創(chuàng)建以及動畫中的一些約定說明。
如圖所示是二叉樹中的一個節(jié)點，這個節(jié)點有左子樹與右子樹，通過兩根綠色的連接線，將此節(jié)點劃分成了三個區(qū)域，我們分別用前、中、后這三個輔助點來表示。
這三個點表明在二叉樹的遍歷中什么時候要取出此節(jié)點的值。
任何一個節(jié)點去遍歷都是：前-左綠線-中-右綠線-后，這樣的順序遍歷的。
前序遍歷
使用遞歸方式實現前序遍歷的具體過程為：
先訪問根節(jié)點
再序遍歷左子樹
最后序遍歷右子樹
我們來對上圖進行一個充分的說明來理解前序遍歷的遞歸實現方式。
首先訪問了28這個節(jié)點，我們看前輔助點，由于是前序遍歷，那么此刻我們取出該節(jié)點的值28
而后通過左綠線訪問28的左子樹
在16這個節(jié)點中，我們看前輔助點，由于是前序遍歷，取出該節(jié)點的值16
通過左綠線訪問16的左子樹
在13這個節(jié)點中，我們看前輔助點，由于是前序遍歷，取出該節(jié)點的值13
13這個節(jié)點左子樹為空，那么我們左綠線就沒有，然后看中輔助點，由于是前序遍歷，因此不做處理
13這個節(jié)點右子樹為空，那么我們右綠線就沒有，然后看后輔助點，由于是前序遍歷，因此不做處理
而后回到16這個節(jié)點中，看中輔助點，由于是前序遍歷，因此不做處理
而后看16這個節(jié)點的右子樹22這個節(jié)點，看前輔助點，由于是前序遍歷，取出該節(jié)點的值22
代碼實現：
/// 144. Binary Tree Preorder Traversal
/// https://leetcode.com/problems/binary-tree-preorder-traversal/description/
/// 二叉樹的前序遍歷
/// 時間復雜度: O(n), n為樹的節(jié)點個數
/// 空間復雜度: O(h), h為樹的高度
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
__preorderTraversal(root, res);
return res;
}
private:
void __preorderTraversal(TreeNode* node, vector<int> &res){
if(node){
res.push_back(node->val);
__preorderTraversal(node->left, res);
__preorderTraversal(node->right, res);
}
}
};
中序遍歷
使用遞歸方式實現中序遍歷的具體過程為：
先中序遍歷左子樹
再訪問根節(jié)點
最后中序遍歷右子樹
我們來對上圖進行一個充分的說明來理解中序遍歷的遞歸實現方式。
首先訪問了28這個節(jié)點，我們看前輔助點，由于是中序遍歷，因此不做處理
而后通過左綠線訪問28的左子樹
在16這個節(jié)點中，我們看前輔助點，由于是中序遍歷，因此不做處理
通過左綠線訪問16的左子樹
在13這個節(jié)點中，我們看前輔助點，由于是中序遍歷，因此不做處理
13這個節(jié)點左子樹為空，那么我們左綠線就沒有，然后看中輔助點，由于是中序遍歷，取出該節(jié)點的值13
13這個節(jié)點右子樹為空，那么我們右綠線就沒有，然后看后輔助點，由于是中序遍歷，因此不做處理
而后回到16這個節(jié)點中，看中輔助點，由于是中序遍歷，取出該節(jié)點的值16
而后看16這個節(jié)點的右子樹22這個節(jié)點，看前輔助點，由于是中序遍歷，因此不做處理
看中輔助點，由于是中序遍歷，取出該節(jié)點的值22
代碼實現：
/// 94. Binary Tree Inorder Traversal
/// https://leetcode.com/problems/binary-tree-inorder-traversal/solution/
/// 二叉樹的中序遍歷
/// 時間復雜度: O(n), n為樹的節(jié)點個數
/// 空間復雜度: O(h), h為樹的高度
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
__inorderTraversal(root, res);
return res;
}
private:
void __inorderTraversal(TreeNode* node, vector<int> &res){
if( node ){
__inorderTraversal(node->left, res);
res.push_back( node->val );
__inorderTraversal(node->right, res);
}
}
};后序遍歷
使用遞歸方式實現后序遍歷的具體過程為：
先后序遍歷左子樹
再后序遍歷右子樹
最后訪問根節(jié)點
我們來對上圖進行一個充分的說明來理解后序遍歷的遞歸實現方式。
首先訪問了28這個節(jié)點，我們看前輔助點，由于是后序遍歷，因此不做處理
而后通過左綠線訪問28的左子樹
在16這個節(jié)點中，我們看前輔助點，由于是后序遍歷，因此不做處理
通過左綠線訪問16的左子樹
在13這個節(jié)點中，我們看前輔助點，由于是后序遍歷，因此不做處理
13這個節(jié)點左子樹為空，那么我們左綠線就沒有，然后看中輔助點，由于是后序遍歷，因此不做處理
13這個節(jié)點右子樹為空，那么我們右綠線就沒有，然后看后輔助點，由于是后序遍歷，取出該節(jié)點的值13
而后回到16這個節(jié)點中，看中輔助點，由于是后序遍歷，因此不做處理
而后看16這個節(jié)點的右子樹22這個節(jié)點，看前輔助點，由于是中序遍歷，因此不做處理
看中輔助點，由于是后序遍歷，因此不做處理
看后輔助點，由于是后序遍歷，取出該節(jié)點的值16
代碼實現：
/// 145. Binary Tree Postorder Traversal
/// https://leetcode.com/problems/binary-tree-postorder-traversal/description/
/// 二叉樹的后序遍歷
/// 時間復雜度: O(n), n為樹的節(jié)點個數
/// 空間復雜度: O(h), h為樹的高度
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
__postorderTraversal(root, res);
return res;
}
private:
void __postorderTraversal(TreeNode* node, vector<int> &res){
if( node ){
__postorderTraversal(node->left, res);
__postorderTraversal(node->right, res);
res.push_back(node->val);
}
}
};
作者簡介：菠了個菜，本文首發(fā)于個人公眾號「五分鐘學算法」。「五分鐘學算法」是致力于通過各種動畫的形式來描繪出各種數據結構，并圖解 LeetCode 原題的學習平臺。
