C++二叉树反序列化（从字符串重建二叉树的完整指南）

准备工作：定义二叉树节点

首先，我们需要定义二叉树的节点结构：

struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode() : val(0), left(nullptr), right(nullptr) {}    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}};

步骤一：解析输入字符串

假设我们的输入字符串是这样的："1,2,3,null,null,4,5"。我们需要先按逗号分割，得到一个字符串数组：

#include <vector>#include <string>#include <sstream>#include <queue>std::vector<std::string> split(const std::string& data) {    std::vector<std::string> result;    std::stringstream ss(data);    std::string item;    while (getline(ss, item, ',')) {        result.push_back(item);    }    return result;}

步骤二：使用队列重建二叉树

我们使用 广度优先搜索（BFS） 的思想，借助队列逐层构建节点：

TreeNode* deserialize(const std::string& data) {    if (data.empty()) return nullptr;    auto nodes = split(data);    if (nodes[0] == "null") return nullptr;    TreeNode* root = new TreeNode(std::stoi(nodes[0]));    std::queue<TreeNode*> q;    q.push(root);    int i = 1;    while (!q.empty() && i < nodes.size()) {        TreeNode* node = q.front();        q.pop();        // 处理左子节点        if (nodes[i] != "null") {            node->left = new TreeNode(std::stoi(nodes[i]));            q.push(node->left);        }        i++;        // 处理右子节点        if (i < nodes.size() && nodes[i] != "null") {            node->right = new TreeNode(std::stoi(nodes[i]));            q.push(node->right);        }        i++;    }    return root;}

完整示例代码

下面是一个完整的可运行示例：

#include <iostream>#include <vector>#include <string>#include <sstream>#include <queue>struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode() : val(0), left(nullptr), right(nullptr) {}    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}};std::vector<std::string> split(const std::string& data) {    std::vector<std::string> result;    std::stringstream ss(data);    std::string item;    while (getline(ss, item, ',')) {        result.push_back(item);    }    return result;}TreeNode* deserialize(const std::string& data) {    if (data.empty()) return nullptr;    auto nodes = split(data);    if (nodes[0] == "null") return nullptr;    TreeNode* root = new TreeNode(std::stoi(nodes[0]));    std::queue<TreeNode*> q;    q.push(root);    int i = 1;    while (!q.empty() && i < nodes.size()) {        TreeNode* node = q.front();        q.pop();        if (nodes[i] != "null") {            node->left = new TreeNode(std::stoi(nodes[i]));            q.push(node->left);        }        i++;        if (i < nodes.size() && nodes[i] != "null") {            node->right = new TreeNode(std::stoi(nodes[i]));            q.push(node->right);        }        i++;    }    return root;}// 简单的前序遍历用于验证结果void preorder(TreeNode* root) {    if (!root) {        std::cout << "null ";        return;    }    std::cout << root->val << " ";    preorder(root->left);    preorder(root->right);}int main() {    std::string data = "1,2,3,null,null,4,5";    TreeNode* root = deserialize(data);    std::cout << "反序列化后的前序遍历: ";    preorder(root);    std::cout << std::endl;    return 0;}

常见问题与注意事项

• 确保输入字符串格式正确，例如用逗号分隔，空节点用 "null" 表示。
• 注意内存管理：实际项目中建议使用智能指针（如 unique_ptr）避免内存泄漏。
• 该方法适用于 LeetCode二叉树反序列化 类题目（如 LeetCode 297）。

总结

通过本文，你已经掌握了如何在 C++ 中实现 二叉树反序列化。这项技能不仅对理解 C++数据结构教程 至关重要，也是解决算法面试题的关键工具。希望你能动手实践，加深理解！

如果你正在准备面试，不妨多练习 LeetCode二叉树反序列化 相关题目，巩固所学知识。