LeetCode 133克隆图：用node.val作键报错‘值为2的节点不存在’原因咨询

我在解决LeetCode 133题《Clone Graph》时遇到一个奇怪的错误：当用Node实例作为processed_node_map的键时，算法能正常通过；但改用node.val作为键时，会触发错误：Node with value 2 doesn't exist in the original graph.。已知两个关键条件：

• 输入中所有节点的val值唯一
• 触发报错的测试用例里根本没有值为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:
    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

核心原因：全局哈希表的残留污染 #

你把processed_node_map定义成了全局变量，这会导致不同测试用例之间的状态互相干扰：

• 假设有第一个测试用例包含val=2的节点，处理完成后processed_node_map里会留存键为2的条目
• 当运行第二个没有val=2节点的测试用例时，DFS过程中可能因边界逻辑或测试用例的隐性关联，代码尝试访问processed_node_map[2]，但原图中不存在该节点，直接触发报错

而用Node实例作为键时，不同测试用例的节点对象完全独立，前一个测试用例的节点实例不会出现在后一个测试用例中，因此全局哈希表的残留不会影响新测试的执行。

修复方案 #

将processed_node_map移到cloneGraph方法内部，让它成为每个测试用例的局部变量，彻底避免跨用例的状态污染：

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

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        processed_node_map = {}  # 改为方法内局部变量
        def dfs(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(dfs(child))

            clone.neighbors = calculated_neighbors
            
            return clone
        return dfs(node) if node else None

内容的提问来源于stack exchange，提问作者John Vandivier