面试题：从图的遍历到深拷贝的实现

本文主要是介绍面试题：从图的遍历到深拷贝的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

非常好的一道面试题，leetcode上是没有的，记录下。

原题

public class N{public int val;public List<N> list;}

val可以唯一标示一个对象，即不同对象的val值都不相同，给定如下类，要求实现深拷贝，方法定义如下：

N dp(N source) {//待实现
}

分析

相信看到这儿，大家都能想到，深拷贝的主要难点是实现list的深拷贝，刚开始我试着用递归去遍历list中的所有引用，发现找不到递归的终止条件，然后我尝试用栈的方式去存储，发现又绕进了死循环，面试官给了提示，如果把题目N改成这样，你会想到什么？

public class N{public int val;public N next;}

链表，那么List<N>呢？于是恍然大悟，这个题目可以转换为图的遍历，类似与leetcode上的clone graph，但是，这个题中的深拷贝必须排除有环的情况，否则将导致循环依赖，所以这个图要看成一个有向图，因此递归的终止条件应该是找到没有依赖的节点，并层层往上拷贝，代码如下：

package testCalculate;import java.util.*;/*** @author jhz* @date 19-6-11 下午11:27*/
public class DeepCloneUtil {/*** 宽度优先搜索(BFS, Breadth First Search)* BFS使用队列(queue)来实施算法过程*/private static Queue<N> queue = new LinkedList<N>();private static Map<N, Boolean> status = new HashMap<N, Boolean>();/*** 开始点** @param startPoint*/public static void BFSSearch(N startPoint) {//1.把起始点放入queue；queue.add(startPoint);status.put(startPoint, false);bfsLoop();N newN = new N();newN.val = startPoint.val;}private static void bfsLoop() {//  1) 从queue中取出队列头的点；更新状态为已经遍历。N currentQueueHeader = queue.poll(); //出

这篇关于面试题：从图的遍历到深拷贝的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---