C++ sregex_token_iterator解引用转int及二叉树反序列化报错解决

问题背景 #

• 实现目标：不使用std::istringstream/std::ostringstream，基于std::sregex_token_iterator完成二叉树的序列化与反序列化，序列化时值后追加空格，反序列化以空格为分隔符拆分字符串。
• 节点定义：TreeNode(int x) : val(x), left(NULL), right(NULL) {}，需要将迭代器指向的元素转为int类型构造节点。

初始报错 #

初始尝试两种转换写法均抛出std::invalid_argument异常：

// 写法1
int val = stoi(*it);
TreeNode* node = new TreeNode(val);

// 写法2
string item = *it;
int val = stoi(item);
TreeNode* node = new TreeNode(val);

报错信息：

terminate called after throwing an instance of 'std::invalid_argument'
  what():  stoi

第一个错误根因及修复 #

• 根因：序列化函数中直接写data += node->val;，这里是把int类型的val直接作为ASCII字符值追加到字符串，不是写入数字的文本形式，导致拆分出来的子串是不可打印控制字符，stoi无法正常解析。
• 修复：将该行改为data += to_string(node->val);，把整型值转为对应的十进制字符串再写入序列化结果。

修复序列化后出现的迭代器空引用问题 #

修改序列化逻辑后抛出空指针引用错误：

Line 2778: Char 16: runtime error: reference binding to null pointer of type
'const std::__cxx11::regex_token_iterator<__gnu_cxx::__normal_iterator<
const char *, std::__cxx11::basic_string<char>>, char, std::__cxx11::regex_traits<char>>::
value_type' (aka 'const sub_match<__gnu_cxx::__normal_iterator<const char *, std::__cxx11::
basic_string<char>>>') (regex.h)

尝试在递归函数开头加边界判断if (it == it_end) return nullptr;后又触发stl_vector.h的越界错误：

Line 1056: Char 34: runtime error: addition of unsigned offset to 0x6080000000a0 overflowed to 0x608000000058 (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1061:34

该问题根因 #

1. 私有serialize函数递归调用时漏传data参数，原代码写的是serialize(node->left);和serialize(node->right);，实际应该传入data引用，否则递归过程会操作临时空字符串，最终序列化结果完全不符合预期，拆分出的token数量和结构完全错乱。
2. 递归反序列化时，遇到空节点标记#直接返回，没有向后移动迭代器，导致后续迭代器位置一直停在空节点标记处，递归逻辑错乱，最终越界访问end迭代器触发空引用。

完整修复后的可运行代码 #

/*
 * @lc app=leetcode id=297 lang=cpp
 *
 * [297] Serialize and Deserialize Binary Tree
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string data;
        serialize(root, data);
        return data;
    }
   
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        regex rgx {"\\s+"};
        auto it = sregex_token_iterator {data.begin(), data.end(), rgx, -1};
        auto it_end = sregex_token_iterator();
        return deserialize(rgx, it, it_end);
    }
private:
    void serialize(TreeNode* node, string& data) {
        if (!node) {
            data += "# ";
            return;
        }
        data += to_string(node->val);
        data += " ";
        serialize(node->left, data); // 补全递归参数
        serialize(node->right, data);
    }

    TreeNode* deserialize(regex& rgx, sregex_token_iterator& it, sregex_token_iterator& it_end) {
        if (it == it_end) {
            return nullptr;
        }
        string item = *it;
        if (item == "#") {
            ++it; // 空节点也要移动迭代器
            return nullptr;
        }
        int val = stoi(item);
        TreeNode* node = new TreeNode(val);

        ++it;
        node->left = deserialize(rgx, it, it_end);
        ++it;
        node->right = deserialize(rgx, it, it_end);
        return node;
    }
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
// @lc code=end

迭代器类型说明 #

std::sregex_token_iterator解引用得到的是std::sub_match类型，该类型支持隐式转换为std::string，可以直接和字符串字面量做比较，也可以直接传给stoi做解析，之前转换失败和迭代器返回类型无关，核心原因是序列化写入的内容本身不是合法数字字符串。

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