递归实现二叉树前中后遍历

递归三要素：每次写递归想到这三要素
1.确定递归函数的参数以及返回值
2.确定递归的出口
3.确定单层递归的逻辑

二叉树结构体：

struct Treenode{
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

前序遍历：

class Solution {
public:
    void traverpre(TreeNode* node, vector& res)
    {
        if(!node)
            return;
        res.push_back(node->val);
        traverpre(node->left, res);
        traverpre(node->right, res);
    }
    vector preorderTraversal(TreeNode* root) {
        vector res;
        traverpre(root, res);
        return res;
    }
};

中序遍历：

class Solution {
public:
    void traverord(TreeNode* node, vector& res)
    {
        if(!node)
            return;
        traverord(node->left, res);
        res.push_back(node->val);
        traverord(node->right, res);
    }
    vector inorderTraversal(TreeNode* root) {
        vector res;
        traverord(root, res);
        return res;
    }
};

后序遍历：

class Solution {
public:
    void traverpost(TreeNode* node, vector& res)
    {
        if(!node)
            return;
        traverpost(node->left, res);
        traverpost(node->right, res);
        res.push_back(node->val);
    }
    vector postorderTraversal(TreeNode* root) {
        vector res;
        traverpost(root, res);
        return res;
    }
};