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