当前位置:网站首页>[sword finger offer] serialized binary tree
[sword finger offer] serialized binary tree
2022-07-06 08:50:00 【Broken wind boy who keeps his hair】
Their thinking
Serialization , You can use various traversal methods , For example, sequence traversal 、 Recursive traversal traverses the binary tree , The value of each node is spliced into a string during traversal , Note that each node is separated by an identifier , for example ,
, This is to prevent the value of the node from exceeding single digits .
Deserialization is decoded according to the serialization process , Different ways of deserialization have different skills , Next, sequence traversal and preorder traversal are used to solve .
Solution 1 : Sequence traversal
- serialize : Traverse through the queue , Then generate a serialized string , Comparing to conventional .
- Deserialization : It's a little bit difficult . First of all,
res
according to,
Get by segmentation String Arraystrs
, Each position represents the value of a node . Like serialization , You also need to use a queue to operate , Note that you need to get the array every timestrs
Two elements in , That is to build the left and right subtrees of the current node , Then add the left and right subtrees to the queue respectively .
import java.util.*;
public class Solution {
String Serialize(TreeNode root) {
String str = "";
if (root == null)
return str;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
str += root.val + ",";
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
if (top.left == null)
str += "#";
else {
queue.add(top.left);
str += top.left.val;
}
str += ',';
if (top.right == null)
str += "#";
else {
queue.add(top.right);
str += top.right.val;
}
str += ',';
}
return str;
}
TreeNode Deserialize(String str) {
if (str.length() == 0)
return null;
int i = 1;
String strList[] = str.split(",");
TreeNode root = new TreeNode(Integer.parseInt(strList[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
// The left subtree
if (strList[i].equals("#"))
top.left = null;
else {
top.left = new TreeNode(Integer.parseInt(strList[i]));
queue.add(top.left);
}
i++;
// Right subtree
if (strList[i].equals("#"))
top.right = null;
else {
top.right = new TreeNode(Integer.parseInt(strList[i]));
queue.add(top.right);
}
i++;
}
return root;
}
}
Solution 2 : The first sequence traversal
- serialize : Define global string
res
, Record the node value traversed during recursion , After traversing a node , Add... After it,
identifier . - Deserialization : It's a little bit difficult . First of all,
res
according to,
Get by segmentation String Arraystrs
, Each position represents the value of a node . Define global variablesind
, Used to record the current traversal tostrs
The location of , If the current location is#
, Said is empty , Go straight back tonull
; Otherwise, create a new nodenode
, And recursively construct its left and right subtrees , Be careful , Determine whether the array is out of bounds before recursion , Ifinds++
After equal tostrs
The length of , It indicates that the array has been traversed , Return at this timenode
( Note that the judgment of array out of bounds cannot be placed at the beginning , Otherwise, I can't write it down , Because I don't know what to return )
import java.util.*;
public class Solution {
public String res = "";
public int ind = 0;
String Serialize(TreeNode root) {
if (root == null) {
res += "#,";
return res;
}
res += root.val + ",";
Serialize(root.left);
Serialize(root.right);
return res;
}
TreeNode deserialize(String[] strs) {
if (strs[ind].equals("#")) {
ind++;
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(strs[ind]));
ind++;
if (ind >= strs.length)
return node;
node.left = deserialize(strs);
node.right = deserialize(strs);
return node;
}
TreeNode Deserialize(String str) {
String[] strs = str.split(",");
return deserialize(strs);
}
}
边栏推荐
- How to conduct interface test? What are the precautions? Nanny level interpretation
- Purpose of computer F1-F12
- Bottom up - physical layer
- 目标检测——Pytorch 利用mobilenet系列(v1,v2,v3)搭建yolov4目标检测平台
- Swagger setting field required is mandatory
- ESP8266-RTOS物联网开发
- LeetCode:214. 最短回文串
- 角色动画(Character Animation)的现状与趋势
- Current situation and trend of character animation
- R language uses the principal function of psych package to perform principal component analysis on the specified data set. PCA performs data dimensionality reduction (input as correlation matrix), cus
猜你喜欢
C language double pointer -- classic question type
Using C language to complete a simple calculator (function pointer array and callback function)
Tcp/ip protocol
项目连接数据库遇到的问题及解决
Visual implementation and inspection of visdom
LeetCode:221. 最大正方形
Unified ordering background interface product description Chinese garbled
Double pointeur en langage C - - modèle classique
Crash problem of Chrome browser
MongoDB 的安装和基本操作
随机推荐
gcc动态库fPIC和fpic编译选项差异介绍
[MySQL] limit implements paging
个人电脑好用必备软件(使用过)
POI add write excel file
The network model established by torch is displayed by torch viz
Roguelike game into crack the hardest hit areas, how to break the bureau?
Marathon envs project environment configuration (strengthen learning and imitate reference actions)
Image,cv2读取图片的numpy数组的转换和尺寸resize变化
[MySQL] multi table query
【ROS】usb_ Cam camera calibration
vb. Net changes with the window, scales the size of the control and maintains its relative position
CSP first week of question brushing
移位运算符
Navicat Premium 创建MySql 创建存储过程
Screenshot in win10 system, win+prtsc save location
Philosophical enlightenment from single point to distributed
hutool优雅解析URL链接并获取参数
ESP8266-RTOS物联网开发
深度剖析C语言指针
Indentation of tabs and spaces when writing programs for sublime text