用C++写出用递归算法完成两个二叉树的复制

在C++中，你可以使用递归的方式来复制两个二叉树。首先，我们需要定义一个结构体表示二叉树节点，并包含左子树和右子树的指针。然后我们可以编写一个递归函数来完成复制的过程。以下是一个简单的示例：

#include <iostream>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 递归函数用于复制节点
TreeNode* cloneNode(TreeNode* node) {
    if (node == NULL) // 如果节点为空，返回NULL
        return nullptr;
    
    // 创建一个新的节点并复制值
    TreeNode* newNode = new TreeNode(node->val);

    // 递归地复制左子树和右子树
    newNode->left = cloneNode(node->left);
    newNode->right = cloneNode(node->right);

    return newNode;
}

// 主函数示例，用于创建原树并复制
void copyAndPrint(TreeNode* original, TreeNode* copy) {
    if (original != NULL) {
        cout << "Original: " << original->val << endl;
        cout << "Copy:     " << copy->val << endl;
        
        copyAndPrint(original->left, copy->left);
        copyAndPrint(original->right, copy->right);
    }
}

int main() {
    // 创建原始二叉树...
    TreeNode* originalTree = ...; // 这里需要实际构建原始树

    // 复制二叉树
    TreeNode* copiedTree = cloneNode(originalTree);

    // 打印或操作复制后的树
    cout << "Copied Tree:" << endl;
    copyAndPrint(originalTree, copiedTree);

    return 0;
}

在这个例子中，`cloneNode`函数负责递归地复制每个节点，而`copyAndPrint`函数则是为了演示如何遍历复制后的树。记得在主函数中实际构造原始树。