二叉树的序列化与反序列化(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:
  2. 1
  3. / \
  4. 2 3
  5. / \
  6. 4 5
  7. 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 {
  2. //序列化
  3. public String serialize(TreeNode root) { //用StringBuilder
  4. StringBuilder res = ser_help(root, new StringBuilder());
  5. return res.toString();
  6. }
  7. public StringBuilder ser_help(TreeNode root, StringBuilder str){
  8. if(null == root){
  9. str.append("null,");
  10. return str;
  11. }
  12. str.append(root.val);
  13. str.append(",");
  14. str = ser_help(root.left, str);
  15. str = ser_help(root.right, str);
  16. return str;
  17. }
  18. //反序列化
  19. public TreeNode deserialize(String data) {
  20. String[] str_word = data.split(",");
  21. List<String> list_word = new LinkedList<String>(Arrays.asList(str_word));
  22. return deser_help(list_word);
  23. }
  24. public TreeNode deser_help(List<String> li){
  25. if(li.get(0).equals("null")){
  26. li.remove(0);
  27. return null;
  28. }
  29. TreeNode res = new TreeNode(Integer.valueOf(li.get(0)));
  30. li.remove(0);
  31. res.left = deser_help(li);
  32. res.right = deser_help(li);
  33. return res;
  34. }
  35. }

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人围观)

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

相关阅读