写一个C++函数，分别通过递归和迭代的方式实现二叉树的前序、中序和后序遍历？

在C++中，我们可以为二叉树的遍历编写递归和迭代两种方法。这里我会提供一个基本的例子，首先我们先定义一个简单的二叉树节点结构：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

接下来，我们将分别展示三种遍历（前序、中序和后序）的递归和非递归版本。

**前序遍历（根-左-右）递归：**

void preorderTraversal(TreeNode* root, vector<int>& res) {
    if (root != nullptr) {
        res.push_back(root->val); // 访问根节点
        preorderTraversal(root->left, res);
        preorderTraversal(root->right, res); // 递归访问左右子树
    }
}

**前序遍历（迭代）：**

void preorderTraversal_iterative(TreeNode* root, stack<TreeNode*>& s, vector<int>& res) {
    stack<TreeNode*> nodeStack;
    while (root || !nodeStack.empty()) {
        while (root) {
            res.push_back(root->val);
            nodeStack.push(root);
            root = root->left;
        }
        root = nodeStack.top(); // 移到下一个未访问的节点
        nodeStack.pop();
        root = root->right;
    }
}

**中序遍历（左-根-右）递归：**

void inorderTraversal(TreeNode* root, vector<int>& res) {
    if (root != nullptr) {
        inorderTraversal(root->left, res);
        res.push_back(root->val);
        inorderTraversal(root->right, res);
    }
}

**中序遍历（迭代）：**

void inorderTraversal_iterative(TreeNode* root, vector<int>& res, stack<TreeNode*>& s) {
    stack<TreeNode*> nodeStack;
    TreeNode* curr = root;
    while (curr || !s.empty()) {
        while (curr) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top(); // 获取并处理当前节点
        s.pop();
        res.push_back(curr->val);
        curr = curr->right;
    }
}

**后序遍历（左-右-根）递归：**

void postorderTraversal(TreeNode* root, vector<int>& res) {
    if (root != nullptr) {
        postorderTraversal(root->left, res);
        postorderTraversal(root->right, res);
        res.push_back(root->val);
    }
}

**后序遍历（迭代）：**

void postorderTraversal_iterative(TreeNode* root, vector<int>& res, stack<TreeNode*> leftStack, stack<TreeNode*>& rightStack) {
    stack<TreeNode*> nodeStack1, nodeStack2;
    nodeStack1.push(root);
    while (!nodeStack1.empty() || !nodeStack2.empty()) {
        while (!nodeStack1.empty()) {
            TreeNode* node = nodeStack1.top();
            nodeStack1.pop();
            res.push_back(node->val);
            if (node->right) {
                nodeStack2.push(node->right);
            }
            if (node->left) {
                nodeStack2.push(node->left);
            }
        }
        if (!nodeStack2.empty()) {
            nodeStack1 = nodeStack2;
            nodeStack2.clear();
        }
    }
}

以上就是二叉树前序、中序和后序遍历的递归和迭代实现。