当前位置： 面试刷题>> 克隆二叉树 (经典算法题500道)
### 题目描述
**题目：克隆二叉树**
给定一棵二叉树，你需要编写一个函数来返回这棵树的深拷贝（克隆）。拷贝的树应与原树有着相同的结构和节点值。
**注意**：
- 你可以假设树中的节点都包含唯一的整数值。
- 无需考虑内存限制，假设有足够的内存来完成这个任务。
### 示例
**输入**：
给定如下二叉树：
```
1
/ \
2 3
/
4
```
**输出**：
应该返回拷贝的二叉树：
```
1
/ \
2 3
/
4
```
### PHP 示例代码
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function cloneTree($root) {
if ($root === null) {
return null;
}
$newNode = new TreeNode($root->val);
$newNode->left = cloneTree($root->left);
$newNode->right = cloneTree($root->right);
return $newNode;
}
// 示例用法
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
$root->left->left = new TreeNode(4);
$clonedRoot = cloneTree($root);
// 此时 $clonedRoot 是原树的深拷贝
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def cloneTree(root):
if root is None:
return None
newNode = TreeNode(root.val)
newNode.left = cloneTree(root.left)
newNode.right = cloneTree(root.right)
return newNode
# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
cloned_root = cloneTree(root)
# 此时 cloned_root 是原树的深拷贝
```
### JavaScript 示例代码
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function cloneTree(root) {
if (!root) {
return null;
}
const newNode = new TreeNode(root.val);
newNode.left = cloneTree(root.left);
newNode.right = cloneTree(root.right);
return newNode;
}
// 示例用法
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
const clonedRoot = cloneTree(root);
// 此时 clonedRoot 是原树的深拷贝
```
**码小课网站中有更多相关内容分享给大家学习**，涵盖算法基础、数据结构、面试技巧等多个方面，欢迎访问。