# 题目

img

```输入：
{"\$id":"1","neighbors":[{"\$id":"2","neighbors":[{"\$ref":"1"},{"\$id":"3","neighbors":[{"\$ref":"2"},{"\$id":"4","neighbors":[{"\$ref":"3"},{"\$ref":"1"}],"val":4}],"val":3}],"val":2},{"\$ref":"4"}],"val":1}

1. 节点数介于 1 到 100 之间。
2. 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
3. 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
4. 必须将给定节点的拷贝作为对克隆图的引用返回。

# 题解

```class Solution {
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> map = new HashMap<>();
Node copyNode = new Node();
copyNode.val = node.val;
map.put(node, copyNode);

while (!queue.isEmpty()) {
Node current = queue.poll();
if (current.neighbors == null) {
continue;
}

if (map.get(current).neighbors == null) {
}

List<Node> neighbors = current.neighbors;
for (Node neighbor : neighbors) {
if (!map.containsKey(neighbor)) {
Node tmp = new Node();
tmp.val = neighbor.val;
map.put(neighbor, tmp);
}
}
}
return map.get(node);
}
}```

```class Solution {
public Node cloneGraph(Node node) {
Map<Node, Node> resNode2CopyNode = new HashMap<>();
return helper(node, resNode2CopyNode);
}

public Node helper(Node node, Map<Node, Node> resNode2CopyNode) {
if (node == null) return null;
if (!resNode2CopyNode.containsKey(node)) {
Node tmp = new Node();
tmp.val = node.val;
resNode2CopyNode.put(node, tmp);
}
Node copy = resNode2CopyNode.get(node);
if (node.neighbors == null) {
return copy;
}

List<Node> neighbors = node.neighbors;
for (Node neighbor : neighbors) {
Node copyNeighbor = null;
if (resNode2CopyNode.containsKey(neighbor)) {
copyNeighbor = resNode2CopyNode.get(neighbor);
} else {
copyNeighbor = helper(neighbor, resNode2CopyNode);
}

}
return copy;
}
}```

```class Solution {
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> resNode2CopyNode = new HashMap<>();
Stack<Node> stack = new Stack<>();
stack.push(node);
Node copy = new Node();
copy.val = node.val;
resNode2CopyNode.put(node, copy);
while (!stack.isEmpty()) {
Node current = stack.pop();
List<Node> neighbors = current.neighbors;
if (neighbors == null) {
continue;
}

Node copyNode = resNode2CopyNode.get(current);
if (copyNode.neighbors == null) {
}

for (Node neighbor : neighbors) {
Node copyNeighbor = null;
if (resNode2CopyNode.containsKey(neighbor)) {
copyNeighbor = resNode2CopyNode.get(neighbor);
} else {
copyNeighbor = new Node();
copyNeighbor.val = neighbor.val;
resNode2CopyNode.put(neighbor, copyNeighbor);
stack.push(neighbor);
}
}
}
return copy;
}
}```

0 条评论

• ### 百度社招面试题——如何用Redis实现分布式锁

关于Redis实现分布式锁的问题，网络上很多，但是很多人的讨论基本就是把原来博主的贴过来，甚至很多面试官也是一知半解经不起推敲就来面候选人，最近结合我自己的学习...

• ### 【Leetcode】129.求根到叶子节点数字之和

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

• ### 【Leetcode】124. 二叉树中的最大路径和

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

• ### LeetCode 133. 克隆图（图的BFS/DFS）

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。

• ### 剑指Offer面试题：16.合并两个排序的链表

PS：这也是一道出镜率极高的面试题，我相信很多童鞋都会很眼熟，就像于千万人之中遇见不期而遇的人，没有别的话可说，唯有轻轻地问一声:“哦,原来你也在这里? ”

• ### 第一章：NodeJS 概述

Node 概述 什么是 Node Node.js® is a JavaScript runtime built on Chrome's V8 JavaScrip...

• ### 【专业技术】Node.js 究竟是什么？

简介 如果您听说过 Node，或者阅读过一些文章，宣称 Node 是多么多么的棒，那么您可能会想：“Node 究竟是什么东西？” 即便是在参阅 Node 的主页...

• ### 深入浅出 Nodejs ( 一 ) ：Nodejs 的简介

我认为 Node 是一门独具风格的技术，它的特点很有意思，本章我们主要讲 Node 的特点，Node 应用场景以及 Node 的使用者。

• ### 按深度打印二叉树节点数据

之前去面试，被问到了一个关于二叉树的问题，本身对算法并不擅长，结果想了半天没想出解决方法，经过面试官提点，才恍然大悟，回来后立马把实现写了出来，详见如下...

• ### 图解 K8S 控制器 Node 生命周期管理

Node其实就对应着kubernetes中的工作组件,今天我们来看下kubernetes中针对Node的生命周期的管理包括心跳检测/污点/容忍/中断等机制的实现...