GeeksforGeeks Burning Tree问题出现SIGABRT错误求排查

问题描述 #

在GeeksforGeeks平台解决「Burning Tree」问题时，代码运行触发Abort signal from abort(3) (SIGABRT)错误。问题需求为：给定一棵二叉树和目标节点，计算点燃目标节点后烧完整棵树的最短时间，每秒火焰会蔓延到当前节点的左子节点、右子节点和父节点。

错误原因分析 #

你的代码存在两个关键问题：

• 无限循环导致内存耗尽：createParentMapping函数的BFS循环中，仅获取队列头部元素front，但从未调用que.pop()。这会让队列永远不会为空，程序陷入无限循环，最终因内存耗尽触发SIGABRT信号。
• 潜在空指针访问风险：若目标节点不存在于树中，targetNode会返回NULL，后续burnTree函数中对NULL节点的left/right成员访问会导致未定义行为。

修复后的代码 #

class Solution {
    // 建立节点到父节点的映射，并返回目标节点
    Node* createParentMapping(Node* root, int target,
                              map<Node*, Node*> &nodeToParent) {
        Node* res = NULL;
        queue<Node*> que;
        que.push(root);
        nodeToParent[root] = NULL;
        while (!que.empty()) {
            Node* front = que.front();
            que.pop(); // 修复：弹出队列头部元素
            if (front->data == target) {
                res = front;
            }
            if (front->left) {
                nodeToParent[front->left] = front;
                que.push(front->left);
            }
            if (front->right) {
                nodeToParent[front->right] = front;
                que.push(front->right);
            }
        }
        return res;
    }

    // 计算烧树时间
    int burnTree(Node* root, map<Node*, Node*> &nodeToParent) {
        if (!root) return 0; // 新增：处理空指针情况
        map<Node*, bool> visited;
        queue<Node*> q;
        q.push(root);
        visited[root] = true;
        int ans = 0;
        while (!q.empty()) {
            bool flag = 0;
            int size = q.size();
            for(int i = 0; i < size; i++) {
                Node* front = q.front();
                q.pop();
                if (front->left && !visited[front->left]) {
                    flag = 1;
                    q.push(front->left);
                    visited[front->left] = 1;
                }
                if (front->right && !visited[front->right]) {
                    flag = 1;
                    q.push(front->right);
                    visited[front->right] = 1;
                }
                if (nodeToParent[front] && !visited[nodeToParent[front]]) {
                    flag = 1;
                    q.push(nodeToParent[front]);
                    visited[nodeToParent[front]] = 1;
                }
            }
            if (flag == 1) {
                ans++;
            }
        }
        return ans;
    }
    
public:
    int minTime(Node* root, int target) {
        map<Node*, Node*> NodeToParent;
        Node* targetNode = createParentMapping(root, target, NodeToParent);
        int time = burnTree(targetNode, NodeToParent);
        return time;
    }
};

关键修复点 #

1. 在createParentMapping的BFS循环中添加que.pop()，确保队列能正常清空，避免无限循环。
2. 在burnTree函数开头增加空指针判断，防止目标节点不存在时的非法内存访问。

内容的提问来源于stack exchange，提问作者sakshi jain