难度: Medium
Submission
运行时间: 51 ms
内存: 19.0 MB
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
"""
class Solution:
def cloneTree(self, root: 'Node') -> 'Node':
if root is None:
return None
# 创建新节点并复制值
new_node = Node(root.val)
# 递归克隆子节点
new_node.children = [self.cloneTree(child) for child in root.children]
return new_node
Explain
此题解采用递归方法克隆 N 叉树。首先检查传入的节点是否为空，如果为空则返回 None。如果节点非空，它首先创建一个新的节点对象，将当前节点的值复制到新节点中。然后，对原始节点的每个子节点递归地调用克隆函数，生成克隆后的子节点列表，并将这些子节点赋值给新节点的子节点列表。这个递归过程将持续进行，直到所有的节点都被克隆完毕。
时间复杂度: O(n)
空间复杂度: O(n)
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
"""
class Solution:
def cloneTree(self, root: 'Node') -> 'Node':
if root is None:
return None # 当树为空时直接返回 None
# 创建新节点并复制根节点的值
new_node = Node(root.val)
# 递归克隆每个子节点，并收集克隆后的子节点列表
new_node.children = [self.cloneTree(child) for child in root.children]
return new_node # 返回克隆后的树的根节点
Explore
在当前实现的递归方法中，如果原树中存在循环引用，该方法将不会正确处理。递归方法会因为无限递归而导致栈溢出错误（stack overflow）。要处理循环引用，我们可以使用一个哈希表来存储已经访问过的节点和它们的克隆副本。在每次递归调用之前，首先检查当前节点是否已经被克隆过，如果是，则直接从哈希表中取出克隆节点，避免重复递归，从而处理循环引用的问题。
在递归方法中，我们首先创建一个新的节点对象，并将当前节点的`val`属性复制到新节点中，这确保了节点值的正确复制。对于`children`属性，我们通过对原节点的每个子节点递归调用克隆函数，并将结果（克隆后的子节点列表）赋值给新节点的`children`属性。这个过程确保了子节点列表的每个元素都被递归地克隆且保持了原有的结构。
在当前的实现中，构造函数`Node`确保如果`children`参数为`None`，它将被初始化为空列表。这种设计可以防止`None`值导致的错误。如果`children`包含非列表类型，这将违反`Node`类的预期用法。在实际应用中，应当在添加节点前验证数据类型，确保`children`总是一个列表。如果需要增强代码的健壮性，可以在克隆方法中添加类型检查，确保`children`属性值的类型正确，从而避免非法类型导致的运行时错误。
递归深度直接受树的高度影响。在高度平衡的树中，递归深度相对较浅，算法效率较高。在极端不平衡的树中，如所有节点都只有一个子节点的线性结构，递归深度与节点数相等，可能导致较高的递归开销。在这种情况下，递归方法的效率较低，因为每增加一个节点，递归深度就增加一层，可能导致栈溢出。在处理极端不平衡的树时，使用迭代方法（例如使用栈）可能更为有效，以避免深层递归带来的性能问题。