(肝了三个小时的困难题-必须记录一下)剑指 Offer 37. 序列化二叉树-----python && C++源代码

简介: (肝了三个小时的困难题-必须记录一下)剑指 Offer 37. 序列化二叉树-----python && C++源代码

剑指 Offer 37. 序列化二叉树


难度困难306收藏分享切换为英文接收动态反馈


请实现两个函数,分别用来序列化和反序列化二叉树。


你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。


提示:输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。


示例:


image.png


输入:root = [1,2,3,null,null,4,5]

输出:[1,2,3,null,null,4,5]

题目思路:

对于我们之前的前序遍历,中序遍历,后序遍历,均没有将null 这个存入我们的数组,因此在这里我们采用层序遍历对于无法访问的空值,存入null到数组即可。


感觉遵循这个思想还是,蛮简单的(但是细节的地方很多,具体看代码把 肝了好久)


Python代码:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        if not root: return '[]'
        queue = collections.deque()
        queue.append(root)
        res = []
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else: res.append('null') 
        return '[' + ','.join(res) + ']'
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        if data=='[]': return
        vals , i = data[1:-1].split(',') , 1
        root = TreeNode(int(vals[0]))
        queue = collections.deque()
        queue.append(root)
        while queue:
            ans_node = queue.popleft()
            if vals[i]!='null':
                ans_node.left = TreeNode(int(vals[i]))
                queue.append(ans_node.left)
            i += 1
            if vals[i]!='null':
                ans_node.right = TreeNode(int(vals[i]))
                queue.append(ans_node.right)
            i += 1
        return root


C++代码:

/**
 * 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 res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            if(node){
                res += to_string(node->val) + ",";  //获取当前节点的值放入res
                q.push(node->left); //先将左节点的值压入队列
                q.push(node->right);  //又节点的值压入队列
            }
            else res += "null,";
        }
        return res.substr(0 , res.size() - 1);
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty())  return nullptr;
        vector<string> s = split(data);
        queue<TreeNode*> q;
        TreeNode* root = new TreeNode(stoi(s[0]));// stoi函数 将n进制的字符串转化为十进制
        q.push(root);
        int i = 1;
        while (!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            if (s[i]!="null"){
                node->left = new TreeNode(stoi(s[i]));
                q.push(node->left);
            }
            i++;
            if (s[i]!="null"){
                node->right = new TreeNode(stoi(s[i]));
                q.push(node->right);
            }
            i++;
        }
        return root;
    }
    vector<string> split(string& s){
        vector<string> res;
        int n = s.size();
        int i = 0;
        while (i<n){
             int j = i+1;
             while (j<n && s[j] != ',') j++;
             res.push_back(s.substr(i , j-i));
             i = j + 1; 
        }
        return res;
    }
};
目录
打赏
0
0
0
0
88
分享
相关文章
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
157 12
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
873 0
|
9月前
|
探索Python与C/C++混合编程的艺术
探索Python与C/C++混合编程的艺术
204 1
为什么Python比C++慢很多?
Python相较于C++较慢主要体现在:动态类型系统导致运行时需解析类型,增加开销;作为解释型语言,逐行转换字节码的过程延长了执行时间;自动内存管理和垃圾回收机制虽简化操作但也带来了额外负担;全局解释器锁(GIL)限制了多线程性能;尽管Python库方便灵活,但在性能上往往不及C++底层库。然而,Python在某些领域如数据分析、机器学习中,凭借其高级别抽象和简洁语法仍表现出色。选语言需依据具体应用场景和需求综合考量。
WK
282 1
|
11月前
|
Python调用C/C++
Python调用C/C++
82 2
|
11月前
|
右手坐标系,空间点绕轴旋转公式&程序(Python和C++程序)
右手坐标系,空间点绕轴旋转公式&程序(Python和C++程序)
420 0
Python 相对于 C++ 有哪些明显的优势
C++是一种强大且高效的编程语言,被广泛应用在系统软件、游戏开发、嵌入式系统等多个领域。然而Python在某些方面展现出显著优势:Python语法简洁直观,易于学习与使用,提高了代码的可读性和团队协作效率;拥有丰富的第三方库和框架资源,能有效提升开发效率;具备良好的跨平台性,无需大量修改即可适应不同操作系统;
WK
213 0
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
46 0
c++的类(附含explicit关键字,友元,内部类)
本文介绍了C++中类的核心概念与用法,涵盖封装、继承、多态三大特性。重点讲解了类的定义(`class`与`struct`)、访问限定符(`private`、`public`、`protected`)、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数(构造函数、析构函数、拷贝构造、赋值重载)以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员(变量与函数)、友元(友元函数与友元类)的概念及其使用场景,并简要介绍了内部类的特性。
115 0

推荐镜像

更多
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问