Serialize and Deserialize Binary Tree
程序员文章站
2022-07-10 10:47:08
...
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
1
/ \
2 3
/ \
4 5
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.
序列化一个二叉树,然后再根据二叉树的序列得到二叉树。我们可以用层序遍历(队列)得到一棵树的序列化,空的节点用n表示,然后在根据序列化生成二叉树,同样借助队列。代码如下:
我们还可以通过DFS得到一个序列,然后在生成二叉树。代码如下:
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
1
/ \
2 3
/ \
4 5
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.
序列化一个二叉树,然后再根据二叉树的序列得到二叉树。我们可以用层序遍历(队列)得到一棵树的序列化,空的节点用n表示,然后在根据序列化生成二叉树,同样借助队列。代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null) return ""; Queue<TreeNode> queue = new LinkedList<TreeNode>(); StringBuilder sb = new StringBuilder(); queue.offer(root); while(!queue.isEmpty()) { TreeNode node = queue.poll(); if(node == null) { sb.append("n "); } else { sb.append(node.val + " "); queue.offer(node.left); queue.offer(node.right); } } return sb.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data == "") return null; String[] string = data.split("\\s"); Queue<TreeNode> queue = new LinkedList<TreeNode>(); TreeNode root = new TreeNode(Integer.parseInt(string[0])); queue.offer(root); for(int i = 1; i < string.length; i++) { TreeNode parent = queue.poll(); if(!string[i].equals("n")) { parent.left = new TreeNode(Integer.parseInt(string[i])); queue.offer(parent.left); } if(++i < string.length && !string[i].equals("n")) { parent.right = new TreeNode(Integer.parseInt(string[i])); queue.offer(parent.right); } } return root; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));
我们还可以通过DFS得到一个序列,然后在生成二叉树。代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null) return ""; Stack<TreeNode> stack = new Stack<TreeNode>(); StringBuilder sb = new StringBuilder(); stack.push(root); while(!stack.isEmpty()) { TreeNode parent = stack.pop(); if(parent == null) { sb.append("n "); } else { sb.append(parent.val + " "); stack.push(parent.right); stack.push(parent.left); } } System.out.println(sb.toString()); return sb.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data == "") return null; String[] string = data.split("\\s"); int[] i = new int[1]; return getNode(string, i); } // 1 2 n n 3 n n private TreeNode getNode(String[] string, int[] i) { if(i[0] >= string.length || string[i[0]].equals("n")) return null; TreeNode root = new TreeNode(Integer.parseInt(string[i[0]])); i[0]++; root.left = getNode(string, i); i[0]++; root.right = getNode(string, i); return root; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));
上一篇: java并发中锁的应用
下一篇: 浅谈Java定时器发展
推荐阅读
-
LC 297 Serialize and Deserialize Binary Tree
-
C#序列化与反序列化(Serialize,Deserialize)实例详解
-
leetcode笔记:Invert Binary Tree
-
Convert Sorted Array to Binary Search Tree
-
minimum-depth-of-binary-tree
-
cf438E. The Child and Binary Tree(生成函数 多项式开根 多项式求逆)
-
【leetcode】-700. Search in a Binary Search Tree 查找二叉搜索树
-
Leetcode——108. Convert Sorted Array to Binary Search Tree
-
Leetcode 108. Convert Sorted Array to Binary Search Tree
-
21天刷题计划之17.1—maximum-depth-of-binary-tree(二叉树的最大深度)(Java语言描述)