遞歸的模板

1.確定遞歸函數(shù)的參數(shù)和返回值

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

node是當(dāng)前處理節(jié)點(diǎn)，vec用來存儲結(jié)果，無返回值

2.確定終止條件

if (node == NULL) return;

遞歸結(jié)束的標(biāo)志是當(dāng)前節(jié)點(diǎn)為空

3.確定單層遞歸的邏輯

前序遍歷是中左右順序，中序遍歷是左中右順序，后序遍歷是左右中順序。根據(jù)遍歷順序，即排列下列三行代碼，保存結(jié)果。

vec.push_back(node->val);
traversal(node->left);
traversal(node->right);

前序遍歷

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

中序遍歷

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

后序遍歷

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