如何优化LeetCode克隆图DFS解法的空间复杂度？

你的DFS解法时间效率拉满，但空间还有优化空间，核心可以从减少哈希表的额外开销和优化递归栈空间两个方向入手，不需要切换到BFS：

1. 用vector替代unordered_map，消除哈希表开销 #

原解法用unordered_map<int, Node*>存储值到新节点的映射，哈希表本身需要维护哈希桶、链表等结构，带来额外空间开销。结合题目条件：所有节点值唯一，且该题测试用例中节点值通常是从1开始的连续整数（1~n），我们可以用vector<Node*>替代哈希表，利用节点值作为索引直接访问，内存连续且无额外哈希开销：

修改后的代码如下：

#include <vector>

using namespace std;

// 题目给定的Node定义
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

class Solution {
public:
    // 用vector替代unordered_map，索引对应节点值
    vector<Node*> mp;
    
    Node* dfs(Node *node){
        // 直接用节点值索引，判断是否已创建
        if (mp[node->val] != nullptr) return mp[node->val];
        mp[node->val] = new Node(node->val);
        for(Node* &i : node->neighbors) {
            mp[node->val]->neighbors.emplace_back(dfs(i));
        }
        return mp[node->val];
    }
    
    Node* cloneGraph(Node* node) {
        if(!node) return nullptr;
        // 题目节点数不超过100，直接设为101足够覆盖所有可能的节点值
        mp.resize(101, nullptr);
        return dfs(node);
    }
};

2. 改用迭代式DFS，优化递归栈空间 #

递归式DFS依赖系统栈，当图是链状结构时，递归深度会达到O(n)，增加空间开销。改用手动维护栈的迭代式DFS，不仅可以避免栈溢出风险，还能更灵活控制空间：

#include <vector>
#include <stack>

using namespace std;

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if(!node) return nullptr;
        
        vector<Node*> mp(101, nullptr);
        stack<Node*> stk;
        stk.push(node);
        mp[node->val] = new Node(node->val);
        
        while(!stk.empty()) {
            Node* curr = stk.top();
            stk.pop();
            
            for(Node* neighbor : curr->neighbors) {
                if(mp[neighbor->val] == nullptr) {
                    mp[neighbor->val] = new Node(neighbor->val);
                    stk.push(neighbor);
                }
                // 给当前新节点添加邻接节点
                mp[curr->val]->neighbors.push_back(mp[neighbor->val]);
            }
        }
        
        return mp[node->val];
    }
};

优化效果说明 #

• vector的内存是连续分配的，相比unordered_map的哈希表结构，减少了大量内存碎片和额外存储开销，空间利用率更高；
• 迭代式DFS用手动栈替代系统递归栈，避免了递归调用的栈帧开销，同时可以更直观地控制内存使用。

这两种优化都保持了DFS的O(n)时间效率，同时能显著提升空间表现。

内容的提问来源于stack exchange，提问作者Tanmay Sharma