C++递归实现前序中序构造二叉树触发SIGABRT错误求助

根据给定的*中序（inorder）和前序（preorder）*遍历序列构造二叉树。

运行错误 #

代码编写完成后运行抛出错误 Abort signal from abort(3) (SIGABRT)，无法定位触发原因。

原代码 #

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;

struct Node{
    int key;
    Node *left, *right;
    Node(int key) {
        this->key = key;
        this->left = this->right = nullptr;
    }
};

class Solution {
public:
    Node *construct_bin(int pidx, int s, int e, map<int, int>  m, vector<int> pre) {
        if (s > e) {
            return nullptr;
        }
        Node * root = new Node(pre[pidx++]);
        int i = m[root->key];
        root->left = construct_bin(pidx, s, i-1, m, pre);
        root->right = construct_bin(pidx, i+1, e, m, pre);
        return root;
    }
};

int main()
{
    Solution sol;
    /* 构造如下二叉树
               1
             /   \
            /     \
           2       3
          /       / \
         /       /   \
        4       5     6
               / \
              /   \
             7     8
    */

    vector<int> inorder = { 4, 2, 1, 7, 5, 8, 3, 6 };
    vector<int> preorder = { 1, 2, 4, 3, 5, 7, 8, 6 };
    map<int, int> m;
    int co = 0;
    for (auto it: inorder) {
        m[it] = co++;
    }
    int n = preorder.size();
    Node* x = sol.construct_bin(0, 0, n-1, m, preorder);
}

实现逻辑参考 #

错误原因 #

1. 核心问题是pidx采用传值方式传递：前序遍历的根节点索引是全局递增的，当前函数内对pidx++的修改只会作用于当前函数栈帧，递归调用左子树时累加的pidx无法同步到上层，导致构造右子树时使用的pidx是错误的旧值，最终访问pre数组越界触发崩溃。
2. 次要问题：map和vector每次递归都传值拷贝，会产生不必要的性能开销，但不是崩溃的直接诱因。

修复方案 #

将pidx改为传引用即可解决崩溃问题，同时可以将map、vector改为const引用优化性能，修改后的核心代码如下：

// 修改函数参数pidx为引用，m和pre改为const引用
Node *construct_bin(int& pidx, int s, int e, const map<int, int>& m, const vector<int>& pre) {
    if (s > e) {
        return nullptr;
    }
    Node * root = new Node(pre[pidx++]);
    int i = m.at(root->key); // 用at替代[]避免节点不存在时插入垃圾数据
    root->left = construct_bin(pidx, s, i-1, m, pre);
    root->right = construct_bin(pidx, i+1, e, m, pre);
    return root;
}

// 调用处也要传入可修改的左值
int pidx = 0;
Node* x = sol.construct_bin(pidx, 0, n-1, m, preorder);

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