题目描述

题目：克隆二叉树

给定一棵二叉树，你需要编写一个函数来返回这棵树的深拷贝（克隆）。拷贝的树应与原树有着相同的结构和节点值。

注意：

• 你可以假设树中的节点都包含唯一的整数值。
• 无需考虑内存限制，假设有足够的内存来完成这个任务。

示例

输入： 给定如下二叉树：

     1
    / \
   2   3
  /
 4

输出： 应该返回拷贝的二叉树：

     1
    / \
   2   3
  /
 4

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 示例代码

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 示例代码

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 是原树的深拷贝

码小课网站中有更多相关内容分享给大家学习，涵盖算法基础、数据结构、面试技巧等多个方面，欢迎访问。