(肝了三个小时的困难题-必须记录一下)剑指 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;
    }
};
相关文章
|
1月前
|
Ubuntu C++ Docker
Docker的基本指令和HTML/PYTHON/C++的简单创建示例
Docker的基本指令和HTML/PYTHON/C++的简单创建示例
|
16天前
|
编译器 开发工具 C++
【Python】已解决error: Microsoft Visual C++ 14.0 or greater is required. Get it with “Microsoft C++ Build
【Python】已解决error: Microsoft Visual C++ 14.0 or greater is required. Get it with “Microsoft C++ Build
79 0
|
22天前
|
算法 Java C++
C++和Python在内存管理上的主要区别是什么?
【7月更文挑战第2天】C++和Python在内存管理上的主要区别是什么?
24 1
|
1月前
|
存储 算法 Python
python常用算法(5)——树,二叉树与AVL树(一)
python常用算法(5)——树,二叉树与AVL树
|
1月前
|
Java Go C#
编程语言C#、C++、Java、Python、go 选择哪个好?
我想说的是,不论选择哪种编程语言,决定选择的都是你最终的目的,做选择之前,先充分调研每一个选择项,再做选择思路就会非常清晰了。
49 3
|
22天前
|
存储 Java 程序员
Python和C++在内存管理方面有什么不同?
【7月更文挑战第2天】Python和C++在内存管理方面有什么不同?
17 0
|
22天前
|
Java C++ 开发者
如何根据项目需求选择使用C++还是Python进行内存管理?
【7月更文挑战第2天】如何根据项目需求选择使用C++还是Python进行内存管理?
21 0
|
22天前
|
算法 Java C++
C++和Python在内存分配策略上的主要区别是什么?
【7月更文挑战第2天】C++和Python在内存分配策略上的主要区别是什么?
17 0
|
22天前
|
Java 程序员 C++
C++和Python在内存分配、释放以及垃圾回收机制上有何不同?
【7月更文挑战第2天】C++和Python在内存分配、释放以及垃圾回收机制上有何不同?
14 0
|
22天前
|
机器学习/深度学习 Java 程序员
Python和C++的区别?
【7月更文挑战第2天】Python和C++的区别?
10 0