克隆图
题目链接: https://leetcode.cn/problems/clone-graph
解题思路:
深度遍历图,从
queue
中取出待遍历节点,对每个节点的Neighbors
进行遍历,对于每个neighbor
判断每个
neighbor
是否为之前遍历过,若遍历过,则从tmpMap
中取出克隆节点,加入临时的neighbors
中否则,构建一个克隆节点,并存入
tmpMap
及queue
中,加入neighbors
中将临时
neighbors
赋值给当前的节点在tmpMap
中的克隆节点直至
queue
为空
复杂度分析
时间复杂度: 时间复杂度为,为图的节点个数
空间复杂度: 空间复杂度为,为图的节点个数
最后更新于