[[410967]]

二叉樹的遞歸遍歷

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

主要是對遞歸不成體系，沒有方法論，每次寫遞歸算法 ，都是靠玄學來寫代碼，代碼能不能編過都靠運氣。

本篇將介紹前后中序的遞歸寫法，一些同學可能會感覺很簡單，其實不然，我們要通過簡單題目把方法論確定下來，有了方法論，后面才能應付復雜的遞歸。

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

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

確定終止條件：寫完了遞歸算法, 運行的時候，經常會遇到棧溢出的錯誤，就是沒寫終止條件或者終止條件寫的不對，操作系統也是用一個棧的結構來保存每一層遞歸的信息，如果遞歸沒有終止，操作系統的內存棧必然就會溢出。

確定單層遞歸的邏輯：確定每一層遞歸需要處理的信息。在這里也就會重復調用自己來實現遞歸的過程。

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

以下以前序遍歷為例：

確定遞歸函數的參數和返回值：因為要打印出前序遍歷節點的數值，所以參數里需要傳入vector在放節點的數值，除了這一點就不需要在處理什么數據了也不需要有返回值，所以遞歸函數返回類型就是void，代碼如下：

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

確定終止條件：在遞歸的過程中，如何算是遞歸結束了呢，當然是當前遍歷的節點是空了，那么本層遞歸就要要結束了，所以如果當前遍歷的這個節點是空，就直接return，代碼如下：

if (cur == NULL) return; 

確定單層遞歸的邏輯：前序遍歷是中左右的循序，所以在單層遞歸的邏輯，是要先取中節點的數值，代碼如下：

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);    // 中 
} 

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

• 144.二叉樹的前序遍歷
• 145.二叉樹的后序遍歷
• 94.二叉樹的中序遍歷

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

其他語言版本

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]: 
        # 保存結果 
        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 

 【編輯推薦】