133。克隆图：原始图中不存在值为 2 的节点

Question

与以下内容相比，我遇到了类似的错误，但根本原因不同：Clone Graph LeetCode 133

考虑下面的实现。如果我对

processed_node_map

使用节点类型密钥，算法就会通过。如果我使用

node.val

作为密钥，我会收到错误：

Node with value 2 doesn't exist in the original graph.

问题：谁能解释一下为什么会出现这个错误？蒂亚

限制和注意事项：

1. Node.val 被限制在输入中的节点之间是唯一的。
2. 此错误出现在没有输入值 2 的测试用例中。

class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

from typing import Optional

processed_node_map = {}

class Solution:
    # solution: https://leetcode.com/problems/clone-graph/solutions/5092202/blind-75-beats-88-06-46-75/
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        return self.dfs(node) if node else None

    def dfs(self, node):
        if node.val in processed_node_map:
            return processed_node_map[node.val]
        
        clone = Node(val=node.val)
        processed_node_map[node.val] = clone

        calculated_neighbors = []
        for child in node.neighbors:
            calculated_neighbors.append(self.dfs(child))

        clone.neighbors = calculated_neighbors
        
        return clone

Answer 1

您可以将您的

processed_node_map

（或访问过的节点）传递给 dfs 方法。

class Solution:
    def cloneGraph(self, node):
        if not node:
            return None
        return self.dfs(node, {})

    def dfs(self, node, processed_node_map):
        if node in processed_node_map:
            return processed_node_map[node]

        cloned_node = Node(node.val)
        processed_node_map[node] = cloned_node

        for neighbor in node.neighbors:

            cloned_neighbor = self.dfs(neighbor, processed_node_map)
            cloned_node.neighbors.append(cloned_neighbor)

        return cloned_node

您将通过以下方式获得 WA（错误答案）：

Node with value 2 doesn't exist in the original graph.

明确指出。

注意

请注意，

Node()

已在其后端定义，但我们不知道其详细信息。您不必重新定义它，您只需拨打他们的

Node()

即可。这个可以删除。

class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []