难度: Medium
Submission
运行时间: 101 ms
内存: 18.2 MB
# Definition for Node.
# class Node:
# def __init__(self, val=0, left=None, right=None, random=None):
# self.val = val
# self.left = left
# self.right = right
# self.random = random
class Solution:
def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':
seen = dict()
def dfs(node):
if not node:
return None
if node in seen:
return seen[node]
nodecopy = NodeCopy(node.val)
seen[node] = nodecopy
nodecopy.left = dfs(node.left)
nodecopy.right = dfs(node.right)
nodecopy.random = dfs(node.random)
return nodecopy
return dfs(root)
Explain
该题解采用了深度优先搜索(DFS)的方法来复制含随机指针的二叉树。使用一个哈希表`seen`来存储已经被访问和复制过的原始节点与其对应的复制节点的映射，以防止重复处理节点并处理可能的循环引用。对于每个被访问的节点，如果它已经在`seen`中，直接返回其对应的复制节点。如果不在`seen`中，创建一个新的复制节点，并将其加入`seen`，然后递归地复制当前节点的左子节点、右子节点和随机指针所指向的节点。最后返回复制的根节点。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for Node.
# class Node:
# def __init__(self, val=0, left=None, right=None, random=None):
# self.val = val
# self.left = left
# self.right = right
# self.random = random
class Solution:
def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':
seen = dict() # 存储已访问节点的原节点与复制节点的映射
def dfs(node):
if not node:
return None # 如果节点为空，则返回None
if node in seen:
return seen[node] # 如果节点已处理过，返回其复制节点
nodecopy = NodeCopy(node.val) # 创建当前节点的复制
seen[node] = nodecopy # 记录原节点与复制节点的映射
nodecopy.left = dfs(node.left) # 递归复制左子树
nodecopy.right = dfs(node.right) # 递归复制右子树
nodecopy.random = dfs(node.random) # 递归复制随机指针指向的节点
return nodecopy # 返回复制的节点
return dfs(root) # 从根节点开始递归复制
Explore
在克隆含随机指针的二叉树问题中，深度优先搜索(DFS)的选择优于广度优先搜索(BFS)出于几个理由。首先，DFS允许我们自然地沿着树的分支深入，直到叶子节点，然后回溯，这种方式非常适合递归实现，代码更简洁。其次，DFS优先创建所有必需的节点，确保当随机指针需要连接到某个特定节点时，该节点已经被创建并可以直接引用。这在BFS中也可以实现，但管理节点创建和它们随机指针的关联通常更复杂，需要额外的数据结构如队列来维护节点的层级状态。
在哈希表`seen`中，键是原始树中的节点，而值是对应的复制树中的节点。通过这种方式，每当访问到一个原始节点时，我们可以检查该节点是否已经被复制。如果已经存在于哈希表中，直接使用映射的复制节点，避免重复创建和递归，这也帮助处理了循环引用的情况。具体实现时，当访问一个节点并决定复制它时，我们创建一个新的节点并将其加入到`seen`中，这样任何后续对原节点的引用都会直接转向已创建的复制节点。
随机指针指向的节点可能为空是一个边界条件，必须在实现中显式处理。在深度优先搜索的递归函数`dfs`中，当访问到一个节点时，首先检查这个节点是否为`None`。如果是，递归函数直接返回`None`。这保证了即使随机指针指向`None`，复制过程也能正确地将复制节点的随机指针设置为`None`。这样的处理确保了复制的树结构和原始树在随机指针的空指向上保持一致。