LeetCode - Hard - 297. Serialize and Deserialize Binary Tree

怼烎@ 2022-10-08 11:21 71阅读 0赞

Topic

  • Tree
  • Design

Description

https://leetcode.com/problems/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.

Clarification: The input/output 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.

Example 1:
9387977615b7e602406be82d7d4452b9.png

  1. Input: root = [1,2,3,null,null,4,5]
  2. Output: [1,2,3,null,null,4,5]

Example 2:

  1. Input: root = []
  2. Output: []

Example 3:

  1. Input: root = [1]
  2. Output: [1]

Example 4:

  1. Input: root = [1,2]
  2. Output: [1,2]

Constraints:

  • The number of nodes in the tree is in the range [ 0 , 1 0 4 ] [0, 10^4] [0,104].
  • − 1000 < = N o d e . v a l < = 1000 -1000 <= Node.val <= 1000 −1000<=Node.val<=1000

Analysis

方法一：自己写的，BFS

方法二：别人写的，前序遍历模式

方法三：别人写的，BFS

Submission

  1. import java.util.Arrays;
  2. import java.util.Deque;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  6. import com.lun.util.BinaryTree.TreeNode;
  8. public class SerializeAndDeserializeBinaryTree { 
  10.     //方法一：自己写的，BFS
  11.     public static class Codec { 
  13.         // Encodes a tree to a single string.
  14.         public String serialize(TreeNode root) { 
  15.             if(root == null) return "";
  16.             StringBuilder sb = new StringBuilder();
  17.             LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
  19.             queue.offer(root);
  21.             int maxDepth = maxDepth(root);
  22.             int currentDepth = 0;
  24.             while(!queue.isEmpty()) { 
  25.                 currentDepth++;
  26.                 for(int size = queue.size(); size > 0; size--) { 
  27.                     TreeNode node = queue.poll();
  28.                     sb.append(node != null ? node.val : "N");
  29.                     sb.append(',');
  31.                     if(node != null && currentDepth != maxDepth) { 
  32.                         queue.offer(node.left);
  33.                         queue.offer(node.right);
  34.                     }
  35.                 }
  36.             }
  38.             return sb.substring(0, sb.length() - 1);
  39.         }
  41.         private int maxDepth(TreeNode node) { 
  42.             if(node == null) return 0;
  43.             return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
  44.         }
  47.         // Decodes your encoded data to tree.
  48.         public TreeNode deserialize(String data) { 
  50.             if(data == null || data.strip().isEmpty())
  51.                 return null;
  53.             TreeNode root = null, parent = null;
  54.             boolean pollFlag = true, sign = false;
  55.             Integer value = null;
  56.             LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
  57.             for(int i = 0; i <= data.length(); i++) { 
  58.                 if(i == data.length() || data.charAt(i) == ',') { 
  60.                     TreeNode node = null;
  61.                     if(value != null) { 
  62.                         node = new TreeNode(value * (sign ? -1 : 1));
  63.                         if(root == null) { 
  64.                             root = node;
  65.                             queue.offer(root);
  66.                             value = null;
  67.                             continue;
  68.                         }
  69.                     }
  71.                     if(pollFlag) { 
  72.                         parent = queue.poll();
  73.                         if(value != null) { 
  74.                             parent.left = node;
  75.                             queue.offer(node);
  76.                         }
  77.                     }else { 
  78.                         if(value != null) { 
  79.                             parent.right = node;
  80.                             queue.offer(node);
  81.                         }
  82.                     }
  83.                     pollFlag = !pollFlag;
  84.                     value = null;
  85.                     sign = false;
  86.                 }else { 
  87.                     if(data.charAt(i) != 'N') { 
  88.                         if(data.charAt(i) == '-') { 
  89.                             sign = true;
  90.                             continue;
  91.                         }
  92.                         if(value == null) value = 0;
  93.                         value = value * 10 + data.charAt(i) - '0'; 
  94.                     }
  95.                 }
  96.             }
  98.             return root;
  99.         }
  100.     }
  102.     //方法二：别人写的，前序遍历模式
  103.     public static class Codec2 { 
  104.         private static final String spliter = ",";
  105.         private static final String NN = "X";
  107.         // Encodes a tree to a single string.
  108.         public String serialize(TreeNode root) { 
  109.             StringBuilder sb = new StringBuilder();
  110.             buildString(root, sb);
  111.             return sb.toString();
  112.         }
  114.         private void buildString(TreeNode node, StringBuilder sb) { 
  115.             if (node == null) { 
  116.                 sb.append(NN).append(spliter);
  117.             } else { 
  118.                 sb.append(node.val).append(spliter);
  119.                 buildString(node.left, sb);
  120.                 buildString(node.right,sb);
  121.             }
  122.         }
  123.         // Decodes your encoded data to tree.
  124.         public TreeNode deserialize(String data) { 
  125.             Deque<String> nodes = new LinkedList<>();
  126.             nodes.addAll(Arrays.asList(data.split(spliter)));
  127.             return buildTree(nodes);
  128.         }
  130.         private TreeNode buildTree(Deque<String> nodes) { 
  131.             String val = nodes.remove();
  132.             if (val.equals(NN)) return null;
  133.             else { 
  134.                 TreeNode node = new TreeNode(Integer.valueOf(val));
  135.                 node.left = buildTree(nodes);
  136.                 node.right = buildTree(nodes);
  137.                 return node;
  138.             }
  139.         }
  140.     }
  142.     //方法三：别人写的，BFS
  143.     public static class Codec3 { 
  144.         public String serialize(TreeNode root) { 
  145.             if (root == null) return "";
  146.             Queue<TreeNode> q = new LinkedList<>();
  147.             StringBuilder res = new StringBuilder();
  148.             q.add(root);
  149.             while (!q.isEmpty()) { 
  150.                 TreeNode node = q.poll();
  151.                 if (node == null) { 
  152.                     res.append("n ");
  153.                     continue;
  154.                 }
  155.                 res.append(node.val + " ");
  156.                 q.add(node.left);
  157.                 q.add(node.right);
  158.             }
  159.             return res.toString();
  160.         }
  162.         public TreeNode deserialize(String data) { 
  163.             if (data == "") return null;
  164.             Queue<TreeNode> q = new LinkedList<>();
  165.             String[] values = data.split(" ");
  166.             TreeNode root = new TreeNode(Integer.parseInt(values[0]));
  167.             q.add(root);
  168.             for (int i = 1; i < values.length; i++) { 
  169.                 TreeNode parent = q.poll();
  170.                 if (!values[i].equals("n")) { 
  171.                     TreeNode left = new TreeNode(Integer.parseInt(values[i]));
  172.                     parent.left = left;
  173.                     q.add(left);
  174.                 }
  175.                 if (!values[++i].equals("n")) { 
  176.                     TreeNode right = new TreeNode(Integer.parseInt(values[i]));
  177.                     parent.right = right;
  178.                     q.add(right);
  179.                 }
  180.             }
  181.             return root;
  182.         }
  183.     }
  185. }

Test

  1. import static org.junit.Assert.*;
  2. import org.junit.Test;
  4. import com.lun.hard.SerializeAndDeserializeBinaryTree.Codec;
  5. import com.lun.hard.SerializeAndDeserializeBinaryTree.Codec2;
  6. import com.lun.hard.SerializeAndDeserializeBinaryTree.Codec3;
  7. import com.lun.util.BinaryTree;
  8. import com.lun.util.BinaryTree.TreeNode;
  10. public class SerializeAndDeserializeBinaryTreeTest { 
  12.     @Test
  13.     public void test() { 
  15.         Codec ser = new Codec();
  16.         Codec deser = new Codec();
  18.         TreeNode node1 = BinaryTree.integers2BinaryTree(1,2,3,null,null,4,5);
  19.         String str1 = ser.serialize(node1);
  20.         assertEquals("1,2,3,N,N,4,5", str1);
  21.         assertTrue(BinaryTree.equals(node1, deser.deserialize(str1)));
  23.         String str2 = ser.serialize(null);
  24.         assertEquals("", str2);
  25.         assertNull(deser.deserialize(str2));
  27.         TreeNode node3 = BinaryTree.integers2BinaryTree(1);
  28.         String str3 = ser.serialize(node3);
  29.         assertEquals("1", str3);
  30.         assertTrue(BinaryTree.equals(node3, deser.deserialize(str3)));
  32.         TreeNode node4 = BinaryTree.integers2BinaryTree(1,2);
  33.         String str4 = ser.serialize(node4);
  34.         assertEquals("1,2,N", str4);
  35.         assertTrue(BinaryTree.equals(node4, deser.deserialize(str4)));
  37.         TreeNode node5 = BinaryTree.integers2BinaryTree(4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2);
  38.         String str5 = ser.serialize(node5);
  39.         assertTrue(BinaryTree.equals(node5, deser.deserialize(str5)));
  41.         TreeNode node6 = BinaryTree.integers2BinaryTree(-1,0,1);
  42.         String str6 = ser.serialize(node6);
  43.         assertTrue(BinaryTree.equals(node6, deser.deserialize(str6)));
  44.     }
  46.     @Test
  47.     public void test2() { 
  49.         Codec2 ser = new Codec2();
  50.         Codec2 deser = new Codec2();
  52.         TreeNode node1 = BinaryTree.integers2BinaryTree(1,2,3,null,null,4,5);
  53.         String str1 = ser.serialize(node1);
  54.         assertTrue(BinaryTree.equals(node1, deser.deserialize(str1)));
  56.         String str2 = ser.serialize(null);
  57.         assertNull(deser.deserialize(str2));
  59.         TreeNode node3 = BinaryTree.integers2BinaryTree(1);
  60.         String str3 = ser.serialize(node3);
  61.         assertTrue(BinaryTree.equals(node3, deser.deserialize(str3)));
  63.         TreeNode node4 = BinaryTree.integers2BinaryTree(1,2);
  64.         String str4 = ser.serialize(node4);
  65.         assertTrue(BinaryTree.equals(node4, deser.deserialize(str4)));
  67.         TreeNode node5 = BinaryTree.integers2BinaryTree(4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2);
  68.         String str5 = ser.serialize(node5);
  69.         assertTrue(BinaryTree.equals(node5, deser.deserialize(str5)));
  71.         TreeNode node6 = BinaryTree.integers2BinaryTree(-1,0,1);
  72.         String str6 = ser.serialize(node6);
  73.         assertTrue(BinaryTree.equals(node6, deser.deserialize(str6)));
  74.     }
  76.     @Test
  77.     public void test3() { 
  79.         Codec3 ser = new Codec3();
  80.         Codec3 deser = new Codec3();
  82.         TreeNode node1 = BinaryTree.integers2BinaryTree(1,2,3,null,null,4,5);
  83.         String str1 = ser.serialize(node1);
  84.         assertTrue(BinaryTree.equals(node1, deser.deserialize(str1)));
  86.         String str2 = ser.serialize(null);
  87.         assertNull(deser.deserialize(str2));
  89.         TreeNode node3 = BinaryTree.integers2BinaryTree(1);
  90.         String str3 = ser.serialize(node3);
  91.         assertTrue(BinaryTree.equals(node3, deser.deserialize(str3)));
  93.         TreeNode node4 = BinaryTree.integers2BinaryTree(1,2);
  94.         String str4 = ser.serialize(node4);
  95.         assertTrue(BinaryTree.equals(node4, deser.deserialize(str4)));
  97.         TreeNode node5 = BinaryTree.integers2BinaryTree(4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2);
  98.         String str5 = ser.serialize(node5);
  99.         assertTrue(BinaryTree.equals(node5, deser.deserialize(str5)));
  101.         TreeNode node6 = BinaryTree.integers2BinaryTree(-1,0,1);
  102.         String str6 = ser.serialize(node6);
  103.         assertTrue(BinaryTree.equals(node6, deser.deserialize(str6)));
  104.     }
  105. }

发表评论

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

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

相关阅读