二叉树的序列化与反序列化(Serialize and Deserialize Binary Tree)

比眉伴天荒 2023-02-18 05:29 114阅读 0赞

二叉树的序列化与反序列化

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.

Example:

  1. You may serialize the following tree:
  3.     1
  4.    / \
  5.   2   3
  6.      / \
  7.     4   5
  9. as "[1,2,3,null,null,4,5]"

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.

思路与代码

Codec

  1. public class Codec { 
  3.     //序列化
  4.     public String serialize(TreeNode root) {       //用StringBuilder
  5.         StringBuilder res = ser_help(root, new StringBuilder());
  6.         return res.toString();
  7.     }
  9.     public StringBuilder ser_help(TreeNode root, StringBuilder str){ 
  10.         if(null == root){ 
  11.             str.append("null,");
  12.             return str;
  13.         }
  14.         str.append(root.val); 
  15.         str.append(",");
  16.         str = ser_help(root.left, str);
  17.         str = ser_help(root.right, str);
  18.         return str;
  19.     }
  21.     //反序列化
  22.     public TreeNode deserialize(String data) { 
  23.         String[] str_word = data.split(",");
  24.         List<String> list_word = new LinkedList<String>(Arrays.asList(str_word));
  25.         return deser_help(list_word);
  26.     }
  28.     public TreeNode deser_help(List<String> li){ 
  29.         if(li.get(0).equals("null")){ 
  30.             li.remove(0);
  31.             return null;
  32.         }
  33.         TreeNode res = new TreeNode(Integer.valueOf(li.get(0)));
  34.         li.remove(0);
  35.         res.left = deser_help(li);
  36.         res.right = deser_help(li);
  37.         return res;
  38.     }
  39. }

TreeNode

  1. /** Definition for a binary tree node. */
  2. public class TreeNode { 
  3.     int val;
  4.     TreeNode left;
  5.     TreeNode right;
  6.     TreeNode(int x) {  val = x; }
  7. }

test

  1. //Your Codec object will be instantiated and called as such:
  2. Codec codec = new Codec();
  3. codec.deserialize(codec.serialize(root));

发表评论

表情：
评论列表 （有 0 条评论，114人围观）

还没有评论，来说两句吧...

相关阅读