二叉樹(shù)的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。

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

前提

在介紹這三組動(dòng)畫(huà)前，我們先用圖來(lái)介紹一下二叉樹(shù)的創(chuàng)建以及動(dòng)畫(huà)中的一些約定說(shuō)明。

如圖所示是二叉樹(shù)中的一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)有左子樹(shù)與右子樹(shù)，通過(guò)兩根綠色的連接線，將此節(jié)點(diǎn)劃分成了三個(gè)區(qū)域，我們分別用前、中、后這三個(gè)輔助點(diǎn)來(lái)表示。

這三個(gè)點(diǎn)表明在二叉樹(shù)的遍歷中什么時(shí)候要取出此節(jié)點(diǎn)的值。

任何一個(gè)節(jié)點(diǎn)去遍歷都是：前-左綠線-中-右綠線-后，這樣的順序遍歷的。

前序遍歷

使用遞歸方式實(shí)現(xiàn)前序遍歷的具體過(guò)程為：

• 先訪問(wèn)根節(jié)點(diǎn)

• 再序遍歷左子樹(shù)

• 最后序遍歷右子樹(shù)

我們來(lái)對(duì)上圖進(jìn)行一個(gè)充分的說(shuō)明來(lái)理解前序遍歷的遞歸實(shí)現(xiàn)方式。

• 首先訪問(wèn)了28這個(gè)節(jié)點(diǎn)，我們看前輔助點(diǎn)，由于是前序遍歷，那么此刻我們?nèi)〕鲈摴?jié)點(diǎn)的值28

• 而后通過(guò)左綠線訪問(wèn)28的左子樹(shù)

• 在16這個(gè)節(jié)點(diǎn)中，我們看前輔助點(diǎn)，由于是前序遍歷，取出該節(jié)點(diǎn)的值16

• 通過(guò)左綠線訪問(wèn)16的左子樹(shù)

• 在13這個(gè)節(jié)點(diǎn)中，我們看前輔助點(diǎn)，由于是前序遍歷，取出該節(jié)點(diǎn)的值13

• 13這個(gè)節(jié)點(diǎn)左子樹(shù)為空，那么我們左綠線就沒(méi)有，然后看中輔助點(diǎn)，由于是前序遍歷，因此不做處理

• 13這個(gè)節(jié)點(diǎn)右子樹(shù)為空，那么我們右綠線就沒(méi)有，然后看后輔助點(diǎn)，由于是前序遍歷，因此不做處理

• 而后回到16這個(gè)節(jié)點(diǎn)中，看中輔助點(diǎn)，由于是前序遍歷，因此不做處理

• 而后看16這個(gè)節(jié)點(diǎn)的右子樹(shù)22這個(gè)節(jié)點(diǎn)，看前輔助點(diǎn)，由于是前序遍歷，取出該節(jié)點(diǎn)的值22

代碼實(shí)現(xiàn)：

中序遍歷

使用遞歸方式實(shí)現(xiàn)中序遍歷的具體過(guò)程為：

• 先中序遍歷左子樹(shù)

• 再訪問(wèn)根節(jié)點(diǎn)

• 最后中序遍歷右子樹(shù)

我們來(lái)對(duì)上圖進(jìn)行一個(gè)充分的說(shuō)明來(lái)理解中序遍歷的遞歸實(shí)現(xiàn)方式。

• 首先訪問(wèn)了28這個(gè)節(jié)點(diǎn)，我們看前輔助點(diǎn)，由于是中序遍歷，因此不做處理

• 而后通過(guò)左綠線訪問(wèn)28的左子樹(shù)

• 在16這個(gè)節(jié)點(diǎn)中，我們看前輔助點(diǎn)，由于是中序遍歷，因此不做處理

• 通過(guò)左綠線訪問(wèn)16的左子樹(shù)

• 在13這個(gè)節(jié)點(diǎn)中，我們看前輔助點(diǎn)，由于是中序遍歷，因此不做處理

• 13這個(gè)節(jié)點(diǎn)左子樹(shù)為空，那么我們左綠線就沒(méi)有，然后看中輔助點(diǎn)，由于是中序遍歷，取出該節(jié)點(diǎn)的值13

• 13這個(gè)節(jié)點(diǎn)右子樹(shù)為空，那么我們右綠線就沒(méi)有，然后看后輔助點(diǎn)，由于是中序遍歷，因此不做處理

• 而后回到16這個(gè)節(jié)點(diǎn)中，看中輔助點(diǎn)，由于是中序遍歷，取出該節(jié)點(diǎn)的值16

• 而后看16這個(gè)節(jié)點(diǎn)的右子樹(shù)22這個(gè)節(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/
/// 二叉樹(shù)的中序遍歷
/// 時(shí)間復(fù)雜度: O(n), n為樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
/// 空間復(fù)雜度: O(h), h為樹(shù)的高度
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)后序遍歷的具體過(guò)程為：

• 先后序遍歷左子樹(shù)

• 再后序遍歷右子樹(shù)

• 最后訪問(wèn)根節(jié)點(diǎn) 

我們來(lái)對(duì)上圖進(jìn)行一個(gè)充分的說(shuō)明來(lái)理解后序遍歷的遞歸實(shí)現(xiàn)方式。

• 首先訪問(wèn)了28這個(gè)節(jié)點(diǎn)，我們看前輔助點(diǎn)，由于是后序遍歷，因此不做處理

• 而后通過(guò)左綠線訪問(wèn)28的左子樹(shù)

• 在16這個(gè)節(jié)點(diǎn)中，我們看前輔助點(diǎn)，由于是后序遍歷，因此不做處理

• 通過(guò)左綠線訪問(wèn)16的左子樹(shù)

• 在13這個(gè)節(jié)點(diǎn)中，我們看前輔助點(diǎn)，由于是后序遍歷，因此不做處理

• 13這個(gè)節(jié)點(diǎn)左子樹(shù)為空，那么我們左綠線就沒(méi)有，然后看中輔助點(diǎn)，由于是后序遍歷，因此不做處理

• 13這個(gè)節(jié)點(diǎn)右子樹(shù)為空，那么我們右綠線就沒(méi)有，然后看后輔助點(diǎn)，由于是后序遍歷，取出該節(jié)點(diǎn)的值13

• 而后回到16這個(gè)節(jié)點(diǎn)中，看中輔助點(diǎn)，由于是后序遍歷，因此不做處理

• 而后看16這個(gè)節(jié)點(diǎn)的右子樹(shù)22這個(gè)節(jié)點(diǎn)，看前輔助點(diǎn)，由于是中序遍歷，因此不做處理

• 看中輔助點(diǎn)，由于是后序遍歷，因此不做處理

• 看后輔助點(diǎn)，由于是后序遍歷，取出該節(jié)點(diǎn)的值16

代碼實(shí)現(xiàn)：