遞歸的模板

1.確定遞歸函數的參數和返回值

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

node是當前處理節點，vec用來存儲結果，無返回值

2.確定終止條件

if (node == NULL) return;

遞歸結束的標志是當前節點為空

3.確定單層遞歸的邏輯

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

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