- 浏览: 174021 次
- 性别:
- 来自: 济南
文章分类
最新评论
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));
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 228Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 230You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 344Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 335Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 454Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 516Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 432Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 623Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 431The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 389Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 521Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 536Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 373All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 866Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 884Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 557Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 603Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 766Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 738You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 631For a undirected graph with tre ...
相关推荐
Serialize and Deserialize Java 示例程序。简单来讲,它的数据格式与json类似,但是在存储时对数字、多字节字符、数组等都做了很多优化,减少了无用的字符,二进制格式,也保证不用字符化带来额外的存储空间的增加...
Deserialize Binary Tree Minimum Window Substring C++ STL中常见容器的时间复杂度 map, set, multimap, and multiset 上述四种容器采用红黑树实现,红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为: 插入:O...
How can we implement trees with nodes that have > 2 children?
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
本文实例讲述了C#序列化与反序列化(Serialize,Deserialize)实现方法。分享给大家供大家参考。具体分析如下: 如果要保存运行程序过程的数据要么保存到数据库中,要么新建一个普通的文件,然后把数据保存进去.但是这...
YamlBeans makes it easy to serialize and deserialize Java object graphs to and from YAML, a human-friendly data format. Replace XML and properties files with YAML for more expressive power (lists, ...
This is a simple Android utils library to write any type of data into cache files and then read them later, using Gson to serialize and deserialize these data. 中文版请看这里。 Gradle compile '...
Serialize and deserialize JSON and XML data Perform encryption and signing to facilitate secure communication between parties Embed and use SQLite databases in your applications Use threads and ...
form-serialize-and-calculate.html
use serde :: {Serialize, Deserialize}; #[derive(Serialize, Deserialize, OpgModel)] #[serde(rename_all = "camelCase" )] #[opg( "Simple enum" )] enum SimpleEnum { Test, Another, Yay, } #[derive...
you don't have a class to serialize or deserialize to, or the JSON is radically different from your class and you need to manually read and write from your objects. LINQ to JSON allows you to easily ...
Alice Bob+-----------------------------------+ +-----------------------------------+| #[derive(Serialize, Deserialize)] | | #[derive(Serialize, Deserialize)] || struct Message | | struct Message |+--...
Json.NET Json.NET is a popular ... you don't have a class to serialize or deserialize to, or the JSON is radically different from your class and you need to manually read and write from your objects.
Tree](Basic-Knowledge/Binary tree.md) Serialize And Deserialize Bit 1.position 2.sequence Sell Stock 区间型 矩阵坐标 Word Ladder Add Two Numbers Matrix Spiral Matrix Mergesort [Algorithm Swap]...
use serde :: {Deserialize, Serialize}; use wactor :: * ; struct Counter { count: u32 , } #[derive(Serialize, Deserialize)] enum Input { AddOne, } #[derive(Serialize, Deserialize, PartialEq, Debug)] ...
安装$ npm install serialize-stl-binary用法 var serializeSTL = require ( 'serialize-stl-binary' ) ;var fs = require ( 'fs' ) ;var mesh = { positions : [ [ - 1.0 , 0.0 , 0.0 ] , [ 0.0 , 1.0 , 0.0 ] , [ ...
软糖 ···· fondant是一个基于宏的库,... // the struct has to derive Serialize, Deserialize and Default use fondant :: Configure; use serde :: {Serialize, Deserialize}; #[derive(Configure, Serialize, D
t have a class to serialize or deserialize to, or the JSON is radically different from your class and you need to manually read and write from your objects.">Json.NET is a popular high-performance ...
struct Counter {count:u32,}#[derive(Serialize,Deserialize)]枚举输入{AddOne,}#[derive(Serialize,Deserialize,PartialEq,Debug)]枚举输出{Count(u32),} impl Actor for Counte