专栏首页爱写BugLeetCode 297:二叉树的序列化与反序列化 Serialize and Deserialize Binary Tree

LeetCode 297:二叉树的序列化与反序列化 Serialize and Deserialize Binary Tree

序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

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

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

示例:

你可以将以下二叉树:

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

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

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态,你的序列化和反序列化算法应该是无状态的。

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

解题思路:

这道题在 LeetCode 中的难度为最高级别 困难,但是实际体验真的很简单,主要考的还是二叉数的遍历。该题的序列化和反序列化各需一个前序遍历,真的非常简单。

Java:

public class Codec {

    public String serialize(TreeNode root) {
        return serializeHelper(root, "");
    }

    private String serializeHelper(TreeNode root, String str) {
        // 基线条件:遇到 null 时构造 “null” 字符串
        if (root == null)
            return str + "null,";
        // 构造返回字符串 str
        str += String.valueOf(root.val) + ",";
        str = serializeHelper(root.left, str);
        str = serializeHelper(root.right, str);
        return str;
    }

    public TreeNode deserialize(String data) {
        String[] data_array = data.split(",");
        // 根据前序遍历的结果逆向构造二叉树时,因为要从左到右操作前序遍历结果,所以使用队列更适合
        Queue<String> list = new LinkedList<>(Arrays.asList(data_array));
        return deserializeHelper(list);
    }

    private TreeNode deserializeHelper(Queue<String> queue) {
        if (queue.peek().equals("null")) {
            queue.poll();
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(queue.poll()));
        root.left = deserializeHelper(queue);
        root.right = deserializeHelper(queue);
        return root;
    }
}

Python

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        def helper(root, string):
            if not root:
                string += "None,"
            else:
                string += str(root.val)+","
                string = helper(root.left, string)
                string = helper(root.right, string)
            return string
        return helper(root, '')

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        def helper(l: list):
            if(l[0] == "None"):
                l.pop(0)
                return None
            root = TreeNode(l.pop(0))
            root.left = helper(l)
            root.right = helper(l)
            return root

        data_list = data.split(',')
        root = helper(data_list)
        return root

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二叉树的最近公共祖先 Lowest Common Ancestor of a Binary Tree

    Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in...

    爱写bug
  • LeetCode 700: 二叉搜索树中的搜索 Search in a Binary Search Tree

    给定二叉搜索树(BST)的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在,则返回 NULL。

    爱写bug
  • LeetCode 450: 删除二叉搜索树中的节点 Delete Node in a BST

    给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节...

    爱写bug
  • TypeScript

    接口(interface)可以用于对【对象的形状(Shape)】进行描述,当然也可以使用interface 描述 class

    九旬大爷
  • Hadoop总结篇之二--yarn的概况

    在弄清楚yarn是什么之前,先来看一下MRv1。 它的由编程模型+数据处理引擎(map/reduceTask)+运行时环境组成(JobTracker/TaskT...

    小端
  • ASP.NET MVC5+EF6+EasyUI 后台管理系统(27)-权限管理系统-分配用户给角色

    分配用户给角色,跟分配角色给用户操作是基本一致的。 打开模块维护,展开SysRole模块添加一个操作码,并赋予权限 ? 设置好之后将权限授权给管理员,在SysR...

    用户1149182
  • zookeeper应用:屏障、队列、分布式锁

    项目地址:https://github.com/windwant/windwant-demo/tree/master/zookeeper-service

    WindWant
  • python pathlib模块的基本使用和总结

    相比常用的 os.path而言,pathlib 对于目录路径的操作更简介也更贴近 Pythonic。但是它不单纯是为了简化操作,还有更大的用途。 pathli...

    叶庭云
  • 在没有技术术语的情况下介绍Adaptive、GBDT、XGboosting等提升算法的原理简介

    这篇文章将不使用任何的术语介绍每个提升算法如何决定每棵树的票数。通过理解这些算法是如何工作的,我们将了解什么时候使用哪种工具。

    deephub
  • 【死磕 Spring】----- IOC 之深入理解 Spring IoC

    在一开始学习 Spring 的时候,我们就接触 IoC 了,作为 Spring 第一个最核心的概念,我们在解读它源码之前一定需要对其有深入的认识,本篇为【死磕 ...

    用户1655470

扫码关注云+社区

领取腾讯云代金券