c++ - 递归克隆图时的stackoverflow

Question

我在使用此版本的代码时遇到错误“AddressSanitizer .. stackoverflow in operator new (unsigned long)”，我在其中使用了copy->neighbors.push_back

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {}
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
unordered_map<Node*, Node*> copies;
Node* cloneGraph(Node* node) {
        if(!node) return node;
        if(copies.find(node)==copies.end()){
            Node *copy = new Node(node->val,{});
            for(auto neighbor:node->neighbors){
                 copy->neighbors.push_back(cloneGraph(neighbor));//stackoverflow 
            }
            copies[node]= copy;
        }
        return copies[node];
}

但它适用于我使用 copies[node]->neighbors.push_back 的这个版本，为什么会这样？
唯一的区别是使用对全局 map 元素的引用:copies[node] 与本地指针copy

Node* cloneGraph(Node* node) {
        if(!node) return node;
        if(copies.find(node)==copies.end()){
            copies[node] = new Node(node->val,{});
            for(auto neighbor:node->neighbors){
                copies[node]->neighbors.push_back(cloneGraph(neighbor));
            }
        }
        return copies[node];
    }

Answer 1

在您的第一个实现中，您将在每次递归调用时创建一个新节点，并将其推送到堆栈。然而，在您的第二个实现中，它被放置在一个数组中，该数组不是局部递归变量的一部分(它看起来像一个全局变量)，因此堆栈不需要跟踪新创建的节点。