复制二叉树
时间: 2023-10-03 10:05:24 浏览: 96
复制二叉树是指创建一棵与原二叉树结构相同、节点值也相同的新二叉树。复制二叉树的算法可以采用递归或迭代的方式实现。下面是递归实现的示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def clone_tree(root):
if not root:
return None
new_root = TreeNode(root.val)
new_root.left = clone_tree(root.left)
new_root.right = clone_tree(root.right)
return new_root
```
在这个示例中,我们定义了一个 `TreeNode` 类表示二叉树节点。 `clone_tree` 函数接收一个二叉树的根节点,并返回一个新的复制二叉树的根节点。如果根节点为空,直接返回 `None` 。否则,创建新节点 `new_root`,将其值设置为原根节点的值,然后递归调用 `clone_tree` 函数,分别将原根节点的左右子树复制到新根节点的左右子树上。最后返回新根节点即可。
相关问题
C语言复制二叉树
复制二叉树可以采用递归的方式,对每个节点进行复制,并递归复制其左右子树。以下是一个用 C 语言实现的例子:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 复制二叉树
TreeNode* copyTree(TreeNode* root) {
if (root == NULL) {
return NULL;
}
TreeNode* new_root = (TreeNode*)malloc(sizeof(TreeNode));
new_root->val = root->val;
new_root->left = copyTree(root->left);
new_root->right = copyTree(root->right);
return new_root;
}
// 中序遍历二叉树
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
int main() {
// 创建二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->left->left = NULL;
root->left->right = NULL;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->right = NULL;
root->right->left->left = NULL;
root->right->left->right = NULL;
// 复制二叉树
TreeNode* new_root = copyTree(root);
// 中序遍历原二叉树和复制后的二叉树
printf("Original tree: ");
inorderTraversal(root);
printf("\n");
printf("Copied tree: ");
inorderTraversal(new_root);
printf("\n");
return 0;
}
```
输出结果为:
```
Original tree: 2 1 4 3
Copied tree: 2 1 4 3
```
可以看到,复制后的二叉树与原二叉树结构相同,并且输出的中序遍历结果也相同。
c语言实现复制二叉树
复制二叉树的C语言实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* cloneTree(struct TreeNode* root) {
if (root == NULL) {
return NULL;
}
struct TreeNode* newRoot = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newRoot->val = root->val;
newRoot->left = cloneTree(root->left);
newRoot->right = cloneTree(root->right);
return newRoot;
}
```