东哥带你刷二叉树(序列化篇) :: labuladong的算法小抄 #992
Replies: 32 comments 5 replies
-
这篇没人吗 |
Beta Was this translation helpful? Give feedback.
-
这篇是不是新加的所以没人 |
Beta Was this translation helpful? Give feedback.
-
这篇感觉看的不是很懂啊🤣 |
Beta Was this translation helpful? Give feedback.
-
前文构造篇不是正好用上了? |
Beta Was this translation helpful? Give feedback.
-
这题感觉就是考二叉树的遍历和构造,其实想清楚了也没什么难的,就是那些小细节折磨人 |
Beta Was this translation helpful? Give feedback.
-
python前序重建二叉树AC代码: # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import collections
from typing import List
NULL = 1001
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
ans = []
def traverse(node):
if not node:
ans.append(NULL)
return
ans.append(node.val)
traverse(node.left)
traverse(node.right)
if not root:
return ""
traverse(root)
return ",".join([str(ele) for ele in ans])
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if data == "":
return None
data = [int(ele) for ele in data.split(",")]
def deserivalize_pre(data: List) -> TreeNode:
if not data:
return None
val = data.popleft()
if val == NULL:
return None
root = TreeNode(val)
root.left = deserivalize_pre(data)
root.right = deserivalize_pre(data)
return root
return deserivalize_pre(collections.deque(data))
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root)) |
Beta Was this translation helpful? Give feedback.
-
/**
* 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.
String NULL = "#";
String SEP = ",";
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serializeHelp(root, sb);
return sb.toString();
}
public void serializeHelp(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(NULL).append(SEP);
return;
}
sb.append(root.val).append(SEP);
serializeHelp(root.left, sb);
serializeHelp(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length() == 0) {
return null;
}
String[] nodes = data.split(",");
TreeNode root = deserializeHello(nodes);
return root;
}
int nodesStart = 0;
public TreeNode deserializeHello(String[] nodes) {
if (nodesStart > nodes.length) {
return null;
}
if (nodes[nodesStart].equals("#")) {
nodesStart++;
return null;
}
int rootVal = new Integer(nodes[nodesStart]);
nodesStart++;
TreeNode root = new TreeNode(rootVal);
root.left = deserializeHello(nodes);
root.right = deserializeHello(nodes);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root)); |
Beta Was this translation helpful? Give feedback.
-
js版本: /**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function (root) {
let res = [];
const traverse = (root) => {
if (root === null) return res.push("Null");
res.push(root.val);
traverse(root.left);
traverse(root.right);
};
traverse(root);
return res.toString();
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data) {
const nodes = data.split(",");
let p = 0;
const deTraverse = (nodes) => {
// if (nodes[0] === "Null") {
// nodes.shift();
if (nodes[p] === "Null") {
p++;
return null;
}
// const root = new TreeNode(parseInt(nodes[0]));
// nodes.shift();
const root = new TreeNode(parseInt(nodes[p]));
p++;
root.left = deTraverse(nodes);
root.right = deTraverse(nodes);
return root;
};
return deTraverse(nodes);
}; |
Beta Was this translation helpful? Give feedback.
-
序列化&反序列化 | 等同于加密&解密。 按照算法加密,在按照算法解密。 |
Beta Was this translation helpful? Give feedback.
-
C++版(感觉就像再考字符串操作,查了一堆字符串string类的操作 😂 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec
{
public:
string StringBuilder;
// 通过前序遍历来进行序列化 间隔符位 , 空指针为 #
void preordercoding(TreeNode *root)
{
if (root == nullptr)
{
StringBuilder.append("#");
StringBuilder.append(",");
return;
}
StringBuilder.append(to_string(root->val));
StringBuilder.append(",");
preordercoding(root->left);
preordercoding(root->right);
}
// Encodes a tree to a single string.
string serialize(TreeNode *root)
{
StringBuilder.clear();
preordercoding(root);
return StringBuilder;
}
// 反序列化
TreeNode *preorderdecoding(string &data)
{
// 字符串已经空了,返回空指针
if (data.empty())
return nullptr;
// 发现是 , 删掉
if (data[0] == ',')
data.erase(data.begin());
// 发现是 # 删掉 并 返回空指针
if (data[0] == '#')
{
data.erase(data.begin());
return nullptr;
}
// 数值获取 以及 删掉字符串中的数值
size_t sz;
TreeNode *root = new TreeNode(stoi(data, &sz));
data.erase(0, sz);
// 递归
root->left = preorderdecoding(data);
root->right = preorderdecoding(data);
// 返回该层完成的树
return root;
}
// Decodes your encoded data to tree.
TreeNode *deserialize(string data)
{
return preorderdecoding(data);
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root)); |
Beta Was this translation helpful? Give feedback.
-
前序的反序列如何判断root.left的长度? |
Beta Was this translation helpful? Give feedback.
-
解题思路Java 代码/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
/**
* 分隔符
*/
final String SPLIT = ",";
/**
* 空节点
*/
final String NULL = "NULL";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
private void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(NULL).append(SPLIT);
return;
}
serialize(root.left, sb);
serialize(root.right, sb);
// 后序遍历位置
sb.append(root.val).append(SPLIT);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
LinkedList<String> nodes = new LinkedList<>();
for (String nodeVal : data.split(SPLIT)) {
nodes.addLast(nodeVal);
}
return deserialize(nodes);
}
private TreeNode deserialize(LinkedList<String> nodes) {
if (nodes.isEmpty()) {
return null;
}
// 后序遍历的最后一个节点,即根节点
String rootVal = nodes.removeLast();
if (NULL.equals(rootVal)) {
return null;
}
// 构造根节点
TreeNode root = new TreeNode(Integer.parseInt(rootVal));
// 先构造右子树,再构造左子树
root.right = deserialize(nodes);
root.left = deserialize(nodes);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root)); |
Beta Was this translation helpful? Give feedback.
-
解题思路Java 层序遍历序列化与反序列化 代码/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
/**
* 分隔符
*/
final String SPLIT = ",";
/**
* 空节点
*/
final String NULL = "NULL";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder sb = new StringBuilder();
// 新建队列
Queue<TreeNode> nodes = new LinkedList<>();
nodes.offer(root);
while (!nodes.isEmpty()) {
// 弹出当前节点
TreeNode currentNode = nodes.poll();
// 层序遍历开始
if (currentNode == null) {
sb.append(NULL).append(SPLIT);
continue;
}
sb.append(currentNode.val).append(SPLIT);
// 层序遍历结束
nodes.offer(currentNode.left);
nodes.offer(currentNode.right);
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.isEmpty()) {
return null;
}
String[] nodeValues = data.split(SPLIT);
// 数组的第一个值,就是根节点的值
TreeNode root = new TreeNode(Integer.parseInt(nodeValues[0]));
// 新建队列 存放根节点
Queue<TreeNode> nodes = new LinkedList<>();
nodes.offer(root);
for (int i = 1; i < nodeValues.length; ) {
// 弹出当前节点
TreeNode parent = nodes.poll();
// 获取左节点
String left = nodeValues[i++];
if (!NULL.equals(left)) {
parent.left = new TreeNode(Integer.parseInt(left));
nodes.offer(parent.left);
} else {
parent.left = null;
}
// 获取右节点
String right = nodeValues[i++];
if (!NULL.equals(right)) {
parent.right = new TreeNode(Integer.parseInt(right));
nodes.offer(parent.right);
} else {
parent.right = null;
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root)); |
Beta Was this translation helpful? Give feedback.
-
Python两种方法,附解释和代码前序遍历class Codec:
def serialize(self, root):
"""
用一个list记录,最后转为string导出:前序遍历,空节点计作N,然后用,连接
"""
res = []
def dfs(node):
if not node:
res.append("N")
return
res.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(res)
def deserialize(self, data):
"""
转化为list,然后用i遍历
先确定根节点 root,然后遵循前序遍历的规则,递归生成左右子树
"""
vals = data.split(",")
self.i = 0
def dfs():
if vals[self.i] == "N":
self.i += 1
return None
node = TreeNode(int(vals[self.i]))
self.i += 1
node.left = dfs()
node.right = dfs()
return node
return dfs() 层序遍历class Codec:
def serialize(self, root):
"""
用queue,把root添加进来,如果有值就加入res[],并且更新左右子树,如果是空就跳过。
"""
if not root:
return ""
res = []
queue = collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
if not node:
res.append("N")
continue
res.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
return ",".join(res)
def deserialize(self, data):
if not data:
return None
vals = data.split(",")
root = TreeNode(int(vals[0]))
queue = collections.deque()
queue.append(root)
i = 1
while queue and i < len(vals):
node = queue.popleft()
if vals[i] != "N":
left = TreeNode(int(vals[i]))
node.left = left
queue.append(left)
i += 1
if vals[i] != "N":
right = TreeNode(int(vals[i]))
node.right = right
queue.append(right)
i += 1
return root |
Beta Was this translation helpful? Give feedback.
-
Golang 层序遍历前面一个忘记贴格式了 type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
if root == nil {
return ""
}
queue := []*TreeNode{root}
s := []string{strconv.Itoa(root.Val)}
for len(queue) != 0 {
n := len(queue)
for i := 0; i < n; i++ {
node := queue[i]
if node.Left != nil {
s = append(s, strconv.Itoa(node.Left.Val))
queue = append(queue, node.Left)
} else {
s = append(s, "")
}
if node.Right != nil {
s = append(s, strconv.Itoa(node.Right.Val))
queue = append(queue, node.Right)
} else {
s = append(s, "")
}
}
queue = queue[n:]
}
return strings.Join(s, ",")
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
if data == "" {
return nil
}
s := strings.Split(data, ",")
i := 0
root := &TreeNode{Val: this.Atoi(s[i])}
i++
queue := []*TreeNode{root}
for len(queue) != 0 {
n := len(queue)
for j := 0; j < n; j++ {
node := queue[j]
if s[i] != "" {
node.Left = &TreeNode{Val: this.Atoi(s[i])}
queue = append(queue, node.Left)
} else {
node.Left = nil
}
i++
if s[i] != "" {
node.Right = &TreeNode{Val: this.Atoi(s[i])}
queue = append(queue, node.Right)
} else {
node.Right = nil
}
i++
}
queue = queue[n:]
}
return root
}
func (this *Codec) Atoi(s string) int {
v, _ := strconv.Atoi(s)
return v
} |
Beta Was this translation helpful? Give feedback.
-
打卡 |
Beta Was this translation helpful? Give feedback.
-
C++前序 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
string StringBuilder;
//通过前序遍历来进行序列化,间隔符“,”,空指针为“#”
void preordercoding(TreeNode* root)
{
if (root == nullptr)
{
StringBuilder.append("#");//空指针就加入#号
StringBuilder.append(",");//每一个字符后都得加入逗号,
return;
}
StringBuilder.append(to_string(root->val));//非空加入数值
StringBuilder.append(",");
preordercoding(root->left);
preordercoding(root->right);
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
StringBuilder.clear();//先清空,准备进行构造
preordercoding(root);
return StringBuilder;
}
//反序列化
TreeNode* preorderdecoding(string &data)
{
if (data.empty()) return nullptr;
//如果字符为“,”,则删除
if (data[0] == ',') data.erase(data.begin());
//如果是#说明第一个元素都是这个,返回空指针
if (data[0] == '#')
{
data.erase(data.begin());
return nullptr;
}
//数值获取
auto sz = sizeof(data);//实际上是size_t类型,就是获取字符串的长度
TreeNode* root = new TreeNode(stoi(data, &sz));
//参数2的&不能丢,因为源代码当中是size_t *idx这个指针,所以需要取地址符
//stoi()函数都是只转换字符串的数字部分,如果遇到其它字符的话则停止转换。
data.erase(0, sz);
//递归
root->left = preorderdecoding(data);//因为加入的时候也是先left后right的
root->right = preorderdecoding(data);
//返回该层完成的树
return root;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
return preorderdecoding(data);
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root)); |
Beta Was this translation helpful? Give feedback.
-
Here is the AC solution of Go's version type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
if root == nil {return ""}
s := []string{}
dfs(root, &s)
fmt.Println(s)
return strings.Join(s, ",")
}
func dfs(root *TreeNode, s *[]string) {
if root == nil {
*s = append(*s, "null")
return
}
*s = append(*s, strconv.Itoa(root.Val))
dfs(root.Left, s)
dfs(root.Right, s)
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
if len(data) == 0 {return nil}
s := strings.Split(data, ",")
return build(&s)
}
//
func build(datas *[]string) *TreeNode {
if len(*datas) == 0{return nil}
rootVal := (*datas)[0]
*datas = (*datas)[1:]
if rootVal == "null" {
return nil
}
val, _ := strconv.Atoi(rootVal)
return &TreeNode{
Val: val,
Left: build(datas),
Right: build(datas),
}
} |
Beta Was this translation helpful? Give feedback.
-
use preorder string to representative the tree node:/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// preorder -> serialize
type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
if root == nil {
return "#"
}
return strconv.Itoa(root.Val) + "," + this.serialize(root.Left) + "," + this.serialize(root.Right)
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
s := strings.Split(data, ",")
return build(&s)
}
//
func build(datas *[]string) *TreeNode {
if len(*datas) == 0{return nil}
rootVal := (*datas)[0]
*datas = (*datas)[1:]
if rootVal == "#" {
return nil
}
val, _ := strconv.Atoi(rootVal)
return &TreeNode{
Val: val,
Left: build(datas),
Right: build(datas),
}
}
/**
* Your Codec object will be instantiated and called as such:
* ser := Constructor();
* deser := Constructor();
* data := ser.serialize(root);
* ans := deser.deserialize(data);
*/ use postorder string to representative the tree node:// preorder -> serialize
type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
if root == nil {
return "#"
}
// return this.serialize(root.Left) + "," + strconv.Itoa(root.Val) + "," + this.serialize(root.Right)
return this.serialize(root.Left) + "," + this.serialize(root.Right) + "," + strconv.Itoa(root.Val)
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
s := strings.Split(data, ",")
return build2(&s)
}
func build2(datas *[]string) *TreeNode {
if len(*datas) == 0 {return nil}
ele := (*datas)[len(*datas) - 1]
*datas = (*datas)[:len(*datas) - 1]
if ele == "#" {return nil}
val, _ := strconv.Atoi(ele)
return &TreeNode{
Val: val,
Right: build2(datas),
Left: build2(datas),
}
} |
Beta Was this translation helpful? Give feedback.
-
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/** Encodes a tree to a single string. */
#define SIZE 50000
void traverse(struct TreeNode *tree, char *data, int *index)
{
data[(*index)++] = ',';
if(tree == NULL)
{
data[(*index)++] = '#';
return;
}
int elem = tree->val;
int stack[4], top = 0;
if(elem == 0)
data[(*index)++] = '0';
if(elem < 0)
{
data[(*index)++] = '-';
elem = -elem;
}
while(elem > 0)
{
stack[top++] = elem % 10;
elem /= 10;
}
while(top > 0)
data[(*index)++] = stack[--top] + '0';
traverse(tree->left, data, index);
traverse(tree->right, data, index);
}
char* serialize(struct TreeNode* root)
{
char *data = (char *)malloc(SIZE * sizeof(char));
int index = 0;
traverse(root, data, &index);
data[index] = '\0';
return data;
}
/** Decodes your encoded data to tree. */
struct TreeNode* des(char* data, int *index)
{
(*index)++;
struct TreeNode *tree;
if(data[(*index)] == '#' || data[(*index)] == '\0')
{
tree = NULL;
(*index)++;
}
else
{
int neg_flag = 0, elem = 0;
if(data[(*index)] == '0')
(*index)++;
else
{
if(data[(*index)] == '-')
{
neg_flag = 1;
(*index)++;
}
while(data[(*index)] != ',')
{
elem = 10 * elem + (data[(*index)] - '0');
(*index)++;
}
if(neg_flag)
elem = -elem;
}
tree = (struct TreeNode *)malloc(sizeof(struct TreeNode));
tree->val = elem;
tree->left = des(data, index);
tree->right = des(data, index);
}
return tree;
}
struct TreeNode* deserialize(char* data)
{
int index = 0;
return des(data, &index);
}
// Your functions will be called as such:
// char* data = serialize(root);
// deserialize(data); |
Beta Was this translation helpful? Give feedback.
-
c++解法: /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
string ser;
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == nullptr) return ser;
preorder(root);
return ser;
}
void preorder(TreeNode* root) {
if (root == nullptr) {
ser.append("#");
ser.append(",");
return;
}
ser.append(std::to_string(root->val));
ser.append(",");
preorder(root->left);
preorder(root->right);
}
// Decodes your encoded data to tree.
TreeNode* rdeserialize(vector<string>& dataArray) {
if (dataArray.front() == "#") {
dataArray.erase(dataArray.begin());
return nullptr;
}
TreeNode* root = new TreeNode(stoi(dataArray.front()));
dataArray.erase(dataArray.begin());
root->left = rdeserialize(dataArray);
root->right = rdeserialize(dataArray);
return root;
}
TreeNode* deserialize(string data) {
if (data.empty()) return nullptr;
vector<string> dataArray;
string str;
for (auto& ch : data) {
if (ch == ',') {
dataArray.push_back(str);
str.clear();
} else {
str.push_back(ch);
}
}
if (!str.empty()) {
dataArray.push_back(str);
str.clear();
}
return rdeserialize(dataArray);
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root)); |
Beta Was this translation helpful? Give feedback.
-
前序遍历 golang type Codec struct {
Nodes []string
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
this.serializable(root)
return strings.Join(this.Nodes, ",")
}
func (this *Codec) serializable(root *TreeNode) {
if root == nil {
this.Nodes = append(this.Nodes,"#")
return
}
this.Nodes = append(this.Nodes,strconv.Itoa(root.Val))
this.serializable(root.Left)
this.serializable(root.Right)
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
this.Nodes =[]string{}
for _, v := range strings.Split(data, ",") {
this.Nodes = append(this.Nodes, v)
}
return this.deserializable()
}
func (this *Codec)deserializable() *TreeNode{
if len(this.Nodes) == 0 {
return nil
}
rootVal:=this.Nodes[0]
this.Nodes = this.Nodes[1:]
if rootVal == "#" {
return nil
}
root:= new (TreeNode)
root.Val , _ = strconv.Atoi(rootVal)
root.Left = this.deserializable()
root.Right = this.deserializable()
return root
} |
Beta Was this translation helpful? Give feedback.
-
反序列化可以使用数组作为参数,这点确实没想到。感觉被前面的构造篇局限了思维,只想到要用数组配合左右指针 |
Beta Was this translation helpful? Give feedback.
-
20230116 打卡~层序遍历的正反序列化都用队列进行层序遍历;反序列化通过移动字符串数组下标来取到左右节点的值,从而正确按层序恢复树,思路好棒 |
Beta Was this translation helpful? Give feedback.
-
C++实现 class Codec {
public:
string SEP = ",";
string null = "#";
string serialize(TreeNode* root) {
string str = "";
traverse(root, str);
return str;
}
void traverse(TreeNode* root, string& str){
if(root == NULL) {
str += null + SEP;
return;
}
str += to_string(root->val) + SEP;
traverse(root->left ,str);
traverse(root->right, str);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
istringstream iss(data); //分割成子字符
return destraverse(iss);
}
TreeNode* destraverse(istringstream& iss) {
string val;
getline(iss, val, ','); //把每个子字符存入val ,,以,号分割来存
if (val == null) return nullptr;
TreeNode* root = new TreeNode(stoi(val));
root->left = destraverse(iss);
root->right = destraverse(iss);
return root;
}
}; |
Beta Was this translation helpful? Give feedback.
-
golang前序遍历,使用二进制编码type Codec struct {
null int16
}
func Constructor() Codec {
return Codec{
null: math.MaxInt16,
}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
if root == nil {
return ""
}
buff := bytes.NewBuffer(nil)
this.serializeNode(root, buff)
return buff.String()
}
func (this *Codec) serializeNode(root *TreeNode, buff *bytes.Buffer) {
if root == nil {
binary.Write(buff, binary.LittleEndian, this.null)
return
} else {
binary.Write(buff, binary.LittleEndian, int16(root.Val))
}
this.serializeNode(root.Left, buff)
this.serializeNode(root.Right, buff)
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
if data == "" {
return nil
}
reader := bytes.NewReader([]byte(data))
return this.buildTree(reader)
}
func (this *Codec) buildTree(reader io.Reader) *TreeNode {
val := int16(0)
binary.Read(reader, binary.LittleEndian, &val)
if val == this.null {
return nil
}
root := &TreeNode{Val: int(val)}
root.Left = this.buildTree(reader)
root.Right = this.buildTree(reader)
return root
}
```go |
Beta Was this translation helpful? Give feedback.
-
如果你的序列化结果中不包含空指针的信息,且你会给出两种遍历顺序,那么按照前文 东哥手把手带你刷二叉树(构造篇) 所说,分两种情况: 如果你的序列化结果中包含空指针的信息,且你只给出一种遍历顺序,也要分两种情况: 为啥整棵树中不包含值相同的节点就可以还原一棵二叉树?这个也不一定吧 |
Beta Was this translation helpful? Give feedback.
-
收到了,谢谢~~
|
Beta Was this translation helpful? Give feedback.
-
C++ - BFS - level order traversal 層級遍歷解法
|
Beta Was this translation helpful? Give feedback.
-
收到了,谢谢~~
|
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
文章链接点这里:东哥带你刷二叉树(序列化篇)
评论礼仪 见这里,违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions