当前位置:首页 > 牛客 > 牛客3747题解析:二叉树序列化与反序列化(C++实现)

牛客3747题解析:二叉树序列化与反序列化(C++实现)

3个月前 (07-20)

牛客3747题解析:二叉树序列化与反序列化(C++实现) 二叉树序列化 前序遍历 递归算法 C++实现 二叉树 二叉树反序列化 字符串 牛客题解 第1张

一、题目解读

牛客3747题要求实现二叉树的序列化与反序列化功能。序列化即将二叉转化为字符串,反序列化则将字符串还原为二叉树结构。题目核心在于设计高效的遍历与节点表示方法,需考虑空节点的处理,确保序列化后的数据能完整还原树结构。

二、解题思路

采用前序遍历+递归策略。序列化时,递归遍历二叉树:若节点为空,用“#”占位;非空节点则记录值并递归处理左右子树。反序列化时,通过字符串流逐字符读取,遇“#”创建空节点,遇数字则创建节点并递归构建子树。关键在于利用特殊字符标记空节点,确保序列化与反序列化的逻辑一致性。

三、解题步骤

1. 序列化(Serialize):

○ 创建字符串流(stringstream)存储结果。

○ 递归函数serializeHelper:

    若节点为空,写入“#”;否则写入节点值。

    递归处理左子树与右子树。

○ 将流内容转为字符数组并返回。

2. 反序列化(Deserialize):

○ 将输入字符串转为流,调用deserializeHelper递归构建树。

○ 读取流中字符:若为“#”,返回空;否则创建节点,递归构建左右子树。

○ 返回根节点。

四、代码与注释

class Solution {
private:
    // 序列化辅助函数:递归遍历并写入流
    void serializeHelper(TreeNode* root, stringstream& ss) {
        if (!root) {  // 空节点用“#”标记
            ss << "# ";
            return;
        }
        ss << root->val << " ";  // 非空节点写入值
        serializeHelper(root->left, ss);  // 递归左子树
        serializeHelper(root->right, ss);  // 递归右子树
    }
    
    // 反序列化辅助函数:从流中读取并构建树
    TreeNode* deserializeHelper(stringstream& ss) {
        string val;
        ss >> val;  // 读取下一个字符
        if (val == "#") return nullptr;  // 若为“#”,返回空
        TreeNode* node = new TreeNode(stoi(val));  // 创建节点
        node->left = deserializeHelper(ss);  // 递归构建左子树
        node->right = deserializeHelper(ss);  // 递归构建右子树
        return node;
    }

public:
    // 序列化主函数:调用辅助函数并返回字符数组
    char* Serialize(TreeNode* root) {
        stringstream ss;
        serializeHelper(root, ss);
        string str = ss.str();
        char* res = new char[str.size() + 1];
        strcpy(res, str.c_str());
        return res;
    }
    
    // 反序列化主函数:将字符串转为流并调用辅助函数
    TreeNode* Deserialize(char* str) {
        if (!str) return nullptr;  // 空串直接返回空
        stringstream ss(str);
        return deserializeHelper(ss);
    }
};

五、总结

该解法通过前序遍历结合特殊字符标记,实现了简洁高效的序列化与反序列化。优点:代码结构清晰,递归逻辑易于理解。适用于对空间要求不高但需快速实现的场景,是解决二叉树序列化问题的经典思路。

原创内容 转载请注明出处

分享给朋友:

相关文章

力扣144:递归之美 轻松掌握二叉树前序遍历

力扣144:递归之美 轻松掌握二叉树前序遍历

题目解读二叉树的前序遍历是一种基础但重要的树遍历方式,其遍历顺序为:先访问根节点,然后递归地前序遍历左子树,最后递归地前序遍历右子树。给定一个二叉树的根节点,我们需要按照这个顺序访问所有节点,并将它们...

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

一、题目解读    “生命之树”是一道经典的树形结构问题,要求计算一棵带权树中,以某个节点为根的最大子树权值和。题目输入为n个节点及边信息,每个节点有权值wi,...

牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)

牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)

一、题目解读牛客13279题要求计算给定树的最大高度。题目输入一棵以邻接表形式表示的树(节点从0开始编号),需要输出从根节点到最深叶节点的最长路径长度。树的结构由n个节点和n-1条边构成,保证为连通无...

手搓二叉树构建类代码详解:从入门到实践(适合新手小白)

一、简介和应用二叉树是数据结构中常见的一种树形结构,每个节点最多有两个子节点(左子节点和右子节点)。它广泛应用于算法设计、数据存储与搜索(如二叉搜索树)、表达式解析等领域。本文将通过手写的C++代码,...

牛客NC67题解:汉诺塔递归算法与解题步骤

牛客NC67题解:汉诺塔递归算法与解题步骤

一、题目解读牛客NC67题要求解决汉诺塔问题,这是一个经典的递归算法题目。题目给定整数n,代表汉诺塔中的盘子数量,需要输出将n个盘子从起始柱移动到目标柱的所有步骤。汉诺塔问题规则为:每次只能移动一个盘...

手搓顺序表实现栈 代码详解及新手教程——从原理到实现的完整指南

一、简介和特点顺序栈是一种基于数组实现的后进先出(LIFO)数据结构。通过动态数组管理存储空间,它具备以下特点:1. 数组存储:数据连续存储,支持随机访问,访问效率高。2. 动态扩容:当栈满时自动扩展...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。