[[410967]]

二叉樹的遞歸遍歷

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

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

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

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

確定遞歸函數(shù)的參數(shù)和返回值：確定哪些參數(shù)是遞歸的過程中需要處理的，那么就在遞歸函數(shù)里加上這個(gè)參數(shù)， 并且還要明確每次遞歸的返回值是什么進(jìn)而確定遞歸函數(shù)的返回類型。

確定終止條件：寫完了遞歸算法, 運(yùn)行的時(shí)候，經(jīng)常會(huì)遇到棧溢出的錯(cuò)誤，就是沒寫終止條件或者終止條件寫的不對(duì)，操作系統(tǒng)也是用一個(gè)棧的結(jié)構(gòu)來保存每一層遞歸的信息，如果遞歸沒有終止，操作系統(tǒng)的內(nèi)存棧必然就會(huì)溢出。

確定單層遞歸的邏輯：確定每一層遞歸需要處理的信息。在這里也就會(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é)感覺前后中序遍歷的遞歸太簡(jiǎn)單了，要打迭代法(非遞歸)，別急，我們明天打迭代法，打個(gè)通透!

其他語言版本

Java：

// 前序遍歷·遞歸·LC144_二叉樹的前序遍歷 
class Solution { 
    ArrayList<Integer> preOrderReverse(TreeNode root) { 
        ArrayList<Integer> result = new ArrayList<Integer>(); 
        preOrder(root, result); 
        return result; 
    } 
 
    void preOrder(TreeNode root, ArrayList<Integer> result) { 
        if (root == null) { 
            return; 
        } 
        result.add(root.val);           // 注意這一句 
        preOrder(root.left, result); 
        preOrder(root.right, result); 
    } 
} 
// 中序遍歷·遞歸·LC94_二叉樹的中序遍歷 
class Solution { 
    public List<Integer> inorderTraversal(TreeNode root) { 
        List<Integer> res = new ArrayList<>(); 
        inorder(root, res); 
        return res; 
    } 
 
    void inorder(TreeNode root, List<Integer> list) { 
        if (root == null) { 
            return; 
        } 
        inorder(root.left, list); 
        list.add(root.val);             // 注意這一句 
        inorder(root.right, list); 
    } 
} 
// 后序遍歷·遞歸·LC145_二叉樹的后序遍歷 
class Solution { 
    public List<Integer> postorderTraversal(TreeNode root) { 
        List<Integer> res = new ArrayList<>(); 
        postorder(root, res); 
        return res; 
    } 
 
    void postorder(TreeNode root, List<Integer> list) { 
        if (root == null) { 
            return; 
        } 
        postorder(root.left, list); 
        postorder(root.right, list); 
        list.add(root.val);             // 注意這一句 
    } 
} 

Python：

# 前序遍歷-遞歸-LC144_二叉樹的前序遍歷 
class Solution: 
    def preorderTraversal(self, root: TreeNode) -> List[int]: 
        # 保存結(jié)果 
        result = [] 
         
        def traversal(root: TreeNode): 
            if root == None: 
                return 
            result.append(root.val) # 前序 
            traversal(root.left)    # 左 
            traversal(root.right)   # 右 
 
        traversal(root) 
        return result 
 
# 中序遍歷-遞歸-LC94_二叉樹的中序遍歷 
class Solution: 
    def inorderTraversal(self, root: TreeNode) -> List[int]: 
        result = [] 
 
        def traversal(root: TreeNode): 
            if root == None: 
                return 
            traversal(root.left)    # 左 
            result.append(root.val) # 中序 
            traversal(root.right)   # 右 
 
        traversal(root) 
        return result 
 
# 后序遍歷-遞歸-LC145_二叉樹的后序遍歷 
class Solution: 
    def postorderTraversal(self, root: TreeNode) -> List[int]: 
        result = [] 
 
        def traversal(root: TreeNode): 
            if root == None: 
                return 
            traversal(root.left)    # 左 
            traversal(root.right)   # 右 
            result.append(root.val) # 后序 
 
        traversal(root) 
        return result 

 【編輯推薦】