用C++输出二叉树的前序遍历，包括递归算法和非递归算法

在C++中，二叉树的前序遍历是指先访问根节点，然后递归地访问左子树，最后访问右子树。这里有两种方法来实现这个过程，一种是递归算法，另一种是非递归算法（也称为迭代算法）。

**递归算法：**

void preorderTraversal(TreeNode* root) {
    if (root != NULL) {
        // 访问当前节点
        cout << root->val << " ";
        
        // 递归遍历左子树
        preorderTraversal(root->left);
        
        // 递归遍历右子树
        preorderTraversal(root->right);
    }
}

**非递归算法（栈实现）：**

void preorderTraversalNonRecursive(TreeNode* root) {
    stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();

        // 如果节点未空，打印并压回左右子节点
        if (node != NULL) {
            cout << node->val << " ";
            s.push(node->right);
            s.push(node->left);
        }
    }
}

在这两个版本中，`preorderTraversal`都会对给定的二叉树进行前序遍历。递归算法直观易懂，但可能会导致堆栈溢出；而非递归算法（使用栈）避免了这个问题，但需要更多的内存空间来保存临时节点。