[[351363]]

 ❝一看就會(huì)，一寫(xiě)就廢!❞

這次我們要好好談一談遞歸，為什么很多同學(xué)看遞歸算法都是“一看就會(huì)，一寫(xiě)就廢”。

主要是對(duì)遞歸不成體系，沒(méi)有方法論，「每次寫(xiě)遞歸算法 ，都是靠玄學(xué)來(lái)寫(xiě)代碼」，代碼能不能編過(guò)都靠運(yùn)氣。

「本篇將介紹前后中序的遞歸寫(xiě)法，一些同學(xué)可能會(huì)感覺(jué)很簡(jiǎn)單，其實(shí)不然，我們要通過(guò)簡(jiǎn)單題目把方法論確定下來(lái)，有了方法論，后面才能應(yīng)付復(fù)雜的遞歸?！?/p>

這里幫助大家確定下來(lái)遞歸算法的三個(gè)要素?！该看螌?xiě)遞歸，都按照這三要素來(lái)寫(xiě)，可以保證大家寫(xiě)出正確的遞歸算法!」

1. 「確定遞歸函數(shù)的參數(shù)和返回值：」確定哪些參數(shù)是遞歸的過(guò)程中需要處理的，那么就在遞歸函數(shù)里加上這個(gè)參數(shù)， 并且還要明確每次遞歸的返回值是什么進(jìn)而確定遞歸函數(shù)的返回類(lèi)型。
2. 「確定終止條件：」寫(xiě)完了遞歸算法, 運(yùn)行的時(shí)候，經(jīng)常會(huì)遇到棧溢出的錯(cuò)誤，就是沒(méi)寫(xiě)終止條件或者終止條件寫(xiě)的不對(duì)，操作系統(tǒng)也是用一個(gè)棧的結(jié)構(gòu)來(lái)保存每一層遞歸的信息，如果遞歸沒(méi)有終止，操作系統(tǒng)的內(nèi)存棧必然就會(huì)溢出。
3. 「確定單層遞歸的邏輯：」確定每一層遞歸需要處理的信息。在這里也就會(huì)重復(fù)調(diào)用自己來(lái)實(shí)現(xiàn)遞歸的過(guò)程。

好了，我們確認(rèn)了遞歸的三要素，接下來(lái)就來(lái)練練手：

「以下以前序遍歷為例：」

「確定遞歸函數(shù)的參數(shù)和返回值」：因?yàn)橐蛴〕銮靶虮闅v節(jié)點(diǎn)的數(shù)值，所以參數(shù)里需要傳入vector在放節(jié)點(diǎn)的數(shù)值，除了這一點(diǎn)就不需要在處理什么數(shù)據(jù)了也不需要有返回值，所以遞歸函數(shù)返回類(lèi)型就是void，代碼如下：

void traversal(TreeNode* cur, vector<int>& vec) 

「確定終止條件」：在遞歸的過(guò)程中，如何算是遞歸結(jié)束了呢，當(dāng)然是當(dāng)前遍歷的節(jié)點(diǎn)是空了，那么本層遞歸就要要結(jié)束了，所以如果當(dāng)前遍歷的這個(gè)節(jié)點(diǎn)是空，就直接return，代碼如下：

if (cur == NULL) return; 

「確定單層遞歸的邏輯」：前序遍歷是中左右的循序，所以在單層遞歸的邏輯，是要先取中節(jié)點(diǎn)的數(shù)值，代碼如下：

vec.push_back(cur->val);    // 中 
traversal(cur->left, vec);  // 左 
traversal(cur->right, vec); // 右 

單層遞歸的邏輯就是按照中左右的順序來(lái)處理的，這樣二叉樹(shù)的前序遍歷，基本就寫(xiě)完了，在看一下完整代碼：

前序遍歷：

class Solution { 
public: 
    void traversal(TreeNode* cur, vector<int>& vec) { 
        if (cur == NULL) return; 
        vec.push_back(cur->val);    // 中 
        traversal(cur->left, vec);  // 左 
        traversal(cur->right, vec); // 右 
    } 
    vector<int> preorderTraversal(TreeNode* root) { 
        vector<int> result; 
        traversal(root, result); 
        return result; 
    } 
}; 

那么前序遍歷寫(xiě)出來(lái)之后，中序和后序遍歷就不難理解了，代碼如下：

中序遍歷：

void traversal(TreeNode* cur, vector<int>& vec) { 
       if (cur == NULL) return; 
       traversal(cur->left, vec);  // 左 
       vec.push_back(cur->val);    // 中 
       traversal(cur->right, vec); // 右 
   } 

后序遍歷：

void traversal(TreeNode* cur, vector<int>& vec) { 
        if (cur == NULL) return; 
        traversal(cur->left, vec);  // 左 
        traversal(cur->right, vec); // 右 
        vec.push_back(cur->val);    // 中 
    } 

此時(shí)大家可以做一做leetcode上三道題目，分別是：

• 144.二叉樹(shù)的前序遍歷
• 145.二叉樹(shù)的后序遍歷
• 94.二叉樹(shù)的中序遍歷

可能有同學(xué)感覺(jué)前后中序遍歷的遞歸太簡(jiǎn)單了，要打迭代法(非遞歸)，別急，我們明天打前中后序的迭代法，打個(gè)通透!

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。