[[351363]]

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

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

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

「本篇將介紹前后中序的遞歸寫法，一些同學(xué)可能會(huì)感覺很簡單，其實(shí)不然，我們要通過簡單題目把方法論確定下來，有了方法論，后面才能應(yīng)付復(fù)雜的遞歸。」

這里幫助大家確定下來遞歸算法的三個(gè)要素。「每次寫遞歸，都按照這三要素來寫，可以保證大家寫出正確的遞歸算法!」

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

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

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

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

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

「確定終止條件」：在遞歸的過程中，如何算是遞歸結(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); // 右 

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

前序遍歷：

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; 
    } 
}; 

那么前序遍歷寫出來之后，中序和后序遍歷就不難理解了，代碼如下：

中序遍歷：

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.二叉樹的前序遍歷
• 145.二叉樹的后序遍歷
• 94.二叉樹的中序遍歷

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

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