LeetCode 133. 克隆图

Categories:

题目描述
思路分析
1. 解法一：DFS + 哈希表（推荐）
相似题目

题目描述

✅ 133. 克隆图

思路分析

解法一：DFS + 哈希表（推荐）

核心思路：

用哈希表记录旧节点到新节点的映射，避免重复克隆。

深度优先遍历图，遇到未克隆的节点就新建并递归邻接点。

返回起点的克隆节点。

复杂度分析：

时间复杂度：O(V + E)，其中 V 为节点数，E 为边数。

空间复杂度：O(V)，哈希表与递归栈占用线性空间。

class Solution {
    private final Map<Node, Node> map = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        return dfs(node);
    }

    private Node dfs(Node node) {
        if (map.containsKey(node)) {
            return map.get(node);
        }

        Node copy = new Node(node.val);
        map.put(node, copy);

        // 递归克隆邻接节点
        for (Node nei : node.neighbors) {
            copy.neighbors.add(dfs(nei));
        }

        return copy;
    }
}

func cloneGraph(node *Node) *Node {
	if node == nil {
		return nil
	}

	visited := make(map[*Node]*Node)

	var dfs func(*Node) *Node
	dfs = func(cur *Node) *Node {
		if v, ok := visited[cur]; ok {
			return v
		}

		copy := &Node{Val: cur.Val}
		visited[cur] = copy

		// 递归克隆邻接节点
		for _, nei := range cur.Neighbors {
			copy.Neighbors = append(copy.Neighbors, dfs(nei))
		}

		return copy
	}

	return dfs(node)
}

相似题目

题目	难度	考察点
133. 克隆图	中等	图遍历
207. 课程表	中等	拓扑排序
210. 课程表 II	中等	拓扑排序
399. 除法求值	中等	图搜索
743. 网络延迟时间	中等	最短路

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/66386751