297. Serialize and Deserialize Binary Tree

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.

For example, you may serialize the following tree

\ 2 3 / \

as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ 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.

思路 首先，老规矩，看到二叉树，想到二叉树的三种遍历方式。

然后，这里需要序列化和反序列化二叉树，可以采用的方法很多了。多种遍历方式都可以，只有在序列化和反序列化时采用相同的遍历方式即可。其中较为简单的是前序遍历和层次遍历。

因为采用层次遍历行需要利用队列，会多引入一种数据结构，所以这里采用前序遍历，这种方法也比较容易理解和实现。

序列化，即将二叉树转成字符串。因为二叉树中包含null节点。需要采用一个特殊字符标记，因为这里的二叉树的值都是数字，所以可以采用非数字作为标记，如采用X。每个节点间用,分割。然后就是按照前序遍历的方法，输入二叉树成字符串，较为简单，不再赘述。

反序列化，即将刚才生成的字符串转换成二叉树。首先，将字符串按照,split成字符串数组的形式，该数组中每一个元素即为一个二叉树的节点。 这里本来可以很简单的用一个全局变量记录，当前遍历的数组index，但是因为题目中要求采用stateless的方式，所以必须换种方式。 可以采用List的方式，将已经遍历的节点删除，剩下的就是当该字符串不是X时，按照前序遍历的方式重建二叉树。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Codec { private static final String spliter = ","; private static final String NN = "X"; // Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); buildString(root, sb); return sb.toString(); } private void buildString(TreeNode node, StringBuilder sb) { if (node == null) { sb.append(NN).append(spliter); } else { sb.append(node.val).append(spliter); buildString(node.left, sb); buildString(node.right,sb); } } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { Deque nodes = new LinkedList<>(); nodes.addAll(Arrays.asList(data.split(spliter))); return buildTree(nodes); } private TreeNode buildTree(Deque nodes) { String val = nodes.remove(); if (val.equals(NN)) return null; else { TreeNode node = new TreeNode(Integer.valueOf(val)); node.left = buildTree(nodes); node.right = buildTree(nodes); return node; } }}// Your Codec object will be instantiated and called as such:// Codec codec = new Codec();// codec.deserialize(codec.serialize(root));

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。