[Java]LeetCode297.二叉树的序列化与反序列化|SerializeandDeserializeBinaryTree
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10693873.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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:
You may serialize the following tree:1
/ \
2 3
/ \
4 5
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.
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例:
你可以将以下二叉树：1
/ \
2 3
/ \
4 5
序列化为
"[1,2,3,null,null,4,5]"
提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。
0.5ms
1/** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9*/10publicclass Codec {
11
12private TreeNode n;
13
14// Encodes a tree to a single string.
15public String serialize(TreeNode root) {
16this.n = root;
17returnnull;
18 }
19
20// Decodes your encoded data to tree.
21public TreeNode deserialize(String data) {
22return n;
23 }
24}
25
26// Your Codec object will be instantiated and called as such:
27// Codec codec = new Codec();
28// codec.deserialize(codec.serialize(root));
1ms
1/** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9*/10publicclass Codec {
11 List<Integer> lstNums = new ArrayList<>();
12int ix = 0;
13
14// Encodes a tree to a single string.
15public List<Integer> serialize(TreeNode root){
16if(root == null){
17 lstNums.add(null);
18return lstNums;
19 }
20
21 lstNums.add(root.val);
22 serialize(root.left);
23 serialize(root.right);
24
25return lstNums;
26 }
27
28// Decodes your encoded data to tree.
29public TreeNode deserialize(List<Integer> data){
30if(ix >= data.size() || data.get(ix) == null){
31 ix++;
32returnnull;
33 }
34
35 TreeNode t = new TreeNode(data.get(ix));
36 ix++;
37
38 t.left = deserialize(data);
39 t.right = deserialize(data);
40
41return t;
42 }
43}
44
45// Your Codec object will be instantiated and called as such:
46// Codec codec = new Codec();
47// codec.deserialize(codec.serialize(root));
2ms
1/** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9*/10publicclass Codec {
11
12// Encodes a tree to a single string.
13public String serialize(TreeNode root) {
14 StringBuilder sb = new StringBuilder();
15 traverse(root , sb);
16 sb.deleteCharAt(sb.length() - 1);
17return sb.toString();
18 }
19
20// Decodes your encoded data to tree.
21public TreeNode deserialize(String data) {
22int[] index = newint[1];
23return buildTree(data , index);
24 }
25
26publicvoid traverse(TreeNode root , StringBuilder sb) {
27if (root == null) {
28 sb.append("#,");
29return;
30 }
31 Integer val = root.val;
32 sb.append(val.toString());
33 sb.append(',');
34 traverse(root.left , sb);
35 traverse(root.right , sb);
36 }
37
38public TreeNode buildTree (String data , int[] index) {
39if (index[0] >= data.length()) {
40returnnull;
41 } elseif (data.charAt(index[0]) == '#') {
42 index[0] += 2;
43returnnull;
44 }
45 TreeNode node = new TreeNode(getValue(data , index[0]));
46while(data.charAt(index[0]) != ',') {
47 index[0] ++;
48 }
49 index[0]++;
50 node.left = buildTree (data , index);
51 node.right = buildTree (data , index);
52return node;
53 }
54
55publicint getValue(String data ,int index) {
56int sign = data.charAt(index) == '-' ? -1 : 1;
57int sum = data.charAt(index) == '-' ? 0 : data.charAt(index) - '0';
58 index++;
59while(data.charAt(index) != ',') {
60 sum = sum * 10 + data.charAt(index) - '0';
61 index++;
62 }
63return sum * sign;
64 }
65 }
3ms
1/** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9*/10publicclass Codec {
11
12// Encodes a tree to a single string.
13public String serialize(TreeNode root) {
14if (root == null) {
15return"";
16 }
17
18 StringBuilder sb = new StringBuilder();
19 serialize(root, sb);
20
21return sb.toString();
22 }
23
24publicvoid serialize(TreeNode node, StringBuilder sb) {
25 sb.append(node.val);
26 sb.append(",");
27
28if (node.left != null) {
29 serialize(node.left, sb);
30 }
31else {
32 sb.append("/");
33 }
34
35if (node.right != null) {
36 serialize(node.right, sb);
37 }
38else {
39 sb.append("/");
40 }
41 }
42
43privatechar chs[];
44privateint start;
45
46// Decodes your encoded data to tree.
47public TreeNode deserialize(String data) {
48 chs = data.toCharArray();
49 start = 0;
50
51return deserialize();
52 }
53
54private TreeNode deserialize() {
55 TreeNode root = null;
56 StringBuilder sb = new StringBuilder();
57int i;
58
59for (i = start; i < chs.length; i++) {
60if (chs[i] == ',') {
61break;
62 }
63
64if (chs[i] == '/') {
65break;
66 }
67
68 sb.append(chs[i]);
69 }
70
71 start = i + 1;
72
73if (sb.length() == 0) {
74return root;
75 }
76
77 root = new TreeNode(Integer.valueOf(sb.toString()));
78 root.left = deserialize();
79 root.right = deserialize();
80
81return root;
82 }
83}
84
85// Your Codec object will be instantiated and called as such:
86// Codec codec = new Codec();
87// codec.deserialize(codec.serialize(root));
4ms
1publicclass Codec { 2public String serialize(TreeNode root) { 3 StringBuilder builder = new StringBuilder(); 4 serialize(root, builder); 5return builder.toString(); 6 } 7 8privatevoid serialize(TreeNode node, StringBuilder builder) {
9if (builder.length() > 0) builder.append(',');
10if (node == null) {
11 builder.append('#');
12return;
13 }
14 builder.append(node.val);
15 serialize(node.left, builder);
16 serialize(node.right, builder);
17 }
18
19public TreeNode deserialize(String data) {
20return deserialize(data, newint[]{0});
21 }
22
23private TreeNode deserialize(String data, int[] i) {
24int left = i[0], right = i[0];
25while (right < data.length() && data.charAt(right) != ',') right++;
26 TreeNode node = right > left ? fromValue(data.substring(left, right)) : null;
27 i[0] = ++right;
28if (node != null) {
29 node.left = deserialize(data, i);
30 node.right = deserialize(data, i);
31 }
32return node;
33 }
34
35private TreeNode fromValue(String value) {
36return"#".equals(value) ? null : new TreeNode(Integer.valueOf(value));
37 }
38 }
5ms
1/** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9*/10publicclass Codec {
11
12int index = 0;
13// Encodes a tree to a single string.
14public String serialize(TreeNode root) {
15 StringBuilder sb = new StringBuilder();
16 serialize(root, sb);
17 System.out.println(sb);
18return sb.toString();
19 }
20publicvoid serialize(TreeNode root,StringBuilder sb) {
21if(root==null){
22 sb.append("#,");
23return;
24 }
25 sb.append(root.val+",");
26 serialize(root.left,sb);
27 serialize(root.right,sb);
28 }
29
30// Decodes your encoded data to tree.
31public TreeNode deserialize(String data) {
32 index = 0;
33return deserialize1(data);
34 }
35
36public TreeNode deserialize1(String data){
37if(index>=data.length()) returnnull;
38if(data.charAt(index)=='#'){
39 index+=2;
40returnnull;
41 }
42int cIndex = data.indexOf(',',index);
43if(cIndex==-1)cIndex = data.length();
44//System.out.printf("index %d cIndex %d \n",index,cIndex);
45 TreeNode node = new TreeNode(Integer.valueOf(data.substring(index,cIndex)));
46 index = cIndex+1;
47 node.left = deserialize1(data);
48 node.right = deserialize1(data);
49return node;
50 }
51}
52
53// Your Codec object will be instantiated and called as such:
54// Codec codec = new Codec();
55// codec.deserialize(codec.serialize(root));
以上是 [Java]LeetCode297.二叉树的序列化与反序列化|SerializeandDeserializeBinaryTree 的全部内容， 来源链接： utcz.com/z/509069.html
