关于算法-数据结构:二叉树的序列化与反序列化

26次阅读

共计 2608 个字符，预计需要花费 7 分钟才能阅读完成。

几个月前，笔者加入了一次面试。面试的最初，面试官要求手写“二叉树的序列化与反序列化”。其实咱们在把握了二叉树的算法套路之后，这应该是比较简单的一道题。接下来咱们就来看看如何解决它吧！

序列化。一个经常出现的名词，咱们都晓得 Java Bean 个别都须要继承 Serializable 接口，还须要定义一个serialVersionUID。新多人虽这么用过却不晓得为什么要这么用。所以为了关照新人，咱们先来讲讲序列化是什么，以及为什么须要序列化。

首先援用 Wikipedia 的一段形容

序列化（serialization）在计算机科学的数据处理中，是指将数据结构或对象状态转换成可取用格局（例如存成文件，存于缓冲，或经由网络中发送），以留待后续在雷同或另一台计算机环境中，能复原原先状态的过程。按照序列化格局从新获取字节的后果时，能够利用它来产生与原始对象雷同语义的正本。对于许多对象，像是应用大量援用的简单对象，这种序列化重建的过程并不容易。面向对象中的对象序列化，并不概括之前原始对象所关系的函数。这种过程也称为对象编组（marshalling）。从一系列字节提取数据结构的反向操作，是反序列化（也称为解编组、deserialization、unmarshalling）。

我想维基百科曾经解释的十分具体了，那咱们想想，为什么须要序列化呢？咱们晓得序列化能够将一个对象 ” 存起来 ”，那么，咱们就能够运行时动静的对象进行网络传输、跨平台存储、转储、RPC 等操作。序列化技术能够说是很多技术的祭祀，咱们耳熟能详的 RPC 就是其中一个。

当初咱们曾经对序列化有了一个根本的理解。咱们无妨思考一下序列化的过程。咱们会发现，将一个数组对象序列化很简略，咱们能够将 int[] arr = new int[3];序列化成 ”0,0,0″。将一个对象序列化也很简略，譬如JSON，就是最好的对象形容格局之一。那二叉树该怎么序列化呢？咱们怎么把一个二维的“树”转换成一个一围的“串”呢?

这就须要用到二叉树的遍历, 一说到遍历大家就会感觉序列化也没那么难了, 因为都晓得二叉树的遍历是比拟死板的. 那么到底选用前序还是中序, 或者后序遍历呢? 答案是 ” 轻易 ”。咱们只须要保障序列化和反序列化用的是同一种遍历办法即可。那么接下来，咱们就借着 Leetcode 中的 297. 二叉树的序列化与反序列化来给大家演示一下序列化与反序列化操作。

首先还是回顾一下遍历操作，三种不同的遍历形式区别只在于 逻辑代码 和递归代码 的绝对地位。咱们就以前序遍从来演示。

// 二叉树前序遍历套路。public static void preOrder(TreeNode root){if( root == null) return;
    
    // 前序遍历 逻辑代码
    doSomething();
    
    preOrder(root.left);
    preOrder(root.right);
}

基于这个骨架，咱们来看看二叉树的序列化代码应该怎么写。依照咱们方才的框架，咱们首先应该想到的代码是这样的。

class Codec {
    final String NULL = "null"; // 用 'null' 代替示意空节点;
    final String SEP = ",";
    StringBuilder res = new StringBuilder();
    
    public void serialize(TreeNode root) {if ( root == null) {res.append(NULL);
            res.append(SEP);
        }
        else {res.append(String.valueOf(root.val));
            res.append(SEP);
            serialize(root.left);
            serialize(root.right);
        }
    }
}

然而咱们会发现，明明一个简略的递归，写进去却很简单。而且力扣 297 给的办法签名是这个样子的。String serialize(TreeNode root)。那这样一变，可能萌新们变得无从下手，不会套框架了。咱们来看看怎么在递归中正确的返回咱们想要的后果。

public String serialize(TreeNode root) {if (root == null) return NULL;
        return String.valueOf(root.val) + SEP + serialize(root.left) + SEP + serialize(root.right);
    }

至此，咱们失去的字符串相似于 “1,2,null,null,3,null,null”

绝对序列化来说，反序列化略微麻烦一点，因为办法须要返回一个 TreeNode 节点，所以咱们在一个办法中是无奈实现递归增加元素并返回的。这时候咱们就须要一个辅助办法来独立地实现递归，在另一个办法中返回。

TreeNode helper(List<String> strs) {if (strs.get(0).equals(NULL)) {strs.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(strs.get(0)));
        strs.remove(0);
        root.left = helper(strs);
        root.right = helper(strs);
        return root;
    }

    public TreeNode deserialize(String data) {String[] data_array = data.split(",");
        List<String> data_list = new ArrayList<>(Arrays.asList(data_array));
        return helper(data_list);
    }

这么一看，二叉树的序列化与反序列化是不是很简略呢？然而其实这外面有一个十分重要的前提条件，那就是 ”null”。有的题目会给一个字符串，然而其中的空元素并没有用 null 标识，或者有其余的题目变种，一般来说，咱们都很难从字符串间接结构出二叉树构造。须要通过两种不同的遍历形式确定 root 节点的地位。但总体来说难度不算很大，这里给大家留一个作业，看看本人是否能够触类旁通，对 Leetcode 此类题做一个集中训练，将变种题目也支出囊中。

Bye ~

正文完