克隆二叉树通常采用递归的方法,具体步骤如下:
基本情况:
如果当前节点为空,则返回空节点。
递归情况:
如果当前节点不为空,则创建一个新的节点,并将当前节点的值复制到新节点中。然后递归地克隆左子树和右子树,并将它们分别赋值给新节点的左子节点和右子节点。
```cpp
include
// 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 深度克隆二叉树的函数
TreeNode* cloneTree(TreeNode* root) {
if (root == NULL) {
return NULL;
}
// 创建新节点,并将当前节点的值复制到新节点中
TreeNode* newRoot = new TreeNode(root->val);
// 递归克隆左子树和右子树
newRoot->left = cloneTree(root->left);
newRoot->right = cloneTree(root->right);
return newRoot;
}
// 辅助函数:中序遍历打印二叉树(用于验证克隆结果)
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
std::cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
// 创建一个示例二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 克隆二叉树
TreeNode* clonedRoot = cloneTree(root);
// 打印原始树和克隆树的中序遍历结果
std::cout << "Original tree inorder traversal: ";
inorderTraversal(root);
std::cout << std::endl;
std::cout << "Cloned tree inorder traversal: ";
inorderTraversal(clonedRoot);
std::cout << std::endl;
return 0;
}
```
代码解释:
TreeNode结构体:
定义了二叉树节点的结构,包括节点的值`val`,左子节点`left`和右子节点`right`。
cloneTree函数:
递归地克隆二叉树。如果当前节点为空,返回空节点;否则,创建一个新节点,并将当前节点的值复制到新节点中,然后递归克隆左子树和右子树。
inorderTraversal函数:
中序遍历二叉树,用于验证克隆结果是否正确。
main函数:
创建一个示例二叉树,调用`cloneTree`函数进行克隆,并打印原始树和克隆树的中序遍历结果。
通过这种方式,可以确保每个节点都被正确克隆,并且父子节点的指针关系得以保留。