297. Serialize and Deserialize Binary Tree
leetcode hard
#array#bit-manipulation#csharp#hard#leetcode#queue#recursion#string#tree#two-pointers
Task
Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде.
C# solution
matched/originalpublic class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Codec {
private void Rserialize(TreeNode root, StringBuilder str) {
if (root == null) {
str.Append("null,");
} else {
str.Append(root.val).Append(",");
Rserialize(root.left, str);
Rserialize(root.right, str);
}
}
public string Serialize(TreeNode root) {
StringBuilder str = new StringBuilder();
Rserialize(root, str);
return str.ToString();
}
private TreeNode Rdeserialize(Queue<string> data) {
if (data.Peek() == "null") {
data.Dequeue();
return null;
}
TreeNode root = new TreeNode(int.Parse(data.Dequeue()));
root.left = Rdeserialize(data);
root.right = Rdeserialize(data);
return root;
}
public TreeNode Deserialize(string data) {
Queue<string> dataArray = new Queue<string>(data.Split(new char[] { ',' }));
return Rdeserialize(dataArray);
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Codec {
private void Rserialize(TreeNode root, StringBuilder str) {
if (root == null) {
str.Append("null,");
} else {
str.Append(root.val).Append(",");
Rserialize(root.left, str);
Rserialize(root.right, str);
}
}
public string Serialize(TreeNode root) {
StringBuilder str = new StringBuilder();
Rserialize(root, str);
return str.ToString();
}
private TreeNode Rdeserialize(queue<string> data) {
if (data.Peek() == "null") {
data.Dequeue();
return null;
}
TreeNode root = new TreeNode(int.Parse(data.Dequeue()));
root.left = Rdeserialize(data);
root.right = Rdeserialize(data);
return root;
}
public TreeNode Deserialize(string data) {
queue<string> dataArray = new queue<string>(data.Split(new char[] { ',' }));
return Rdeserialize(dataArray);
}
}Java solution
matched/originalpublic class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Codec {
private void rserialize(TreeNode root, StringBuilder str) {
if (root == null) {
str.append("null,");
} else {
str.append(root.val).append(",");
rserialize(root.left, str);
rserialize(root.right, str);
}
}
public String serialize(TreeNode root) {
StringBuilder str = new StringBuilder();
rserialize(root, str);
return str.toString();
}
private TreeNode rdeserialize(LinkedList<String> data) {
if (data.get(0).equals("null")) {
data.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(data.remove(0)));
root.left = rdeserialize(data);
root.right = rdeserialize(data);
return root;
}JavaScript solution
matched/originalclass TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Codec {
rserialize(root, str) {
if (root === null) {
str.push("null");
} else {
str.push(String(root.val));
this.rserialize(root.left, str);
this.rserialize(root.right, str);
}
}
serialize(root) {
const str = [];
this.rserialize(root, str);
return str.join(",");
}
rdeserialize(data) {
if (data[0] === "null") {
data.shift();
return null;
}
const root = new TreeNode(Number(data.shift()));
root.left = this.rdeserialize(data);
root.right = this.rdeserialize(data);
return root;
}
deserialize(data) {
const dataArray = data.split(",");
return this.rdeserialize(dataArray);
}
}Python solution
matched/originalclass TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Codec:
def rserialize(self, root, string):
if root is None:
string += "null,"
else:
string += str(root.val) + ","
string = self.rserialize(root.left, string)
string = self.rserialize(root.right, string)
return string
def serialize(self, root):
return self.rserialize(root, "")
def rdeserialize(self, data_list):
if data_list[0] == "null":
data_list.pop(0)
return None
root = TreeNode(int(data_list.pop(0)))
root.left = self.rdeserialize(data_list)
root.right = self.rdeserialize(data_list)
return root
def deserialize(self, data):
data_list = data.split(',')
return self.rdeserialize(data_list)Go solution
matched/originalpackage main
import (
"strconv"
"strings"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
type Codec struct{}
func (c *Codec) rserialize(root *TreeNode, str *strings.Builder) {
if root == nil {
str.WriteString("null,")
} else {
str.WriteString(strconv.Itoa(root.Val) + ",")
c.rserialize(root.Left, str)
c.rserialize(root.Right, str)
}
}
func (c *Codec) serialize(root *TreeNode) string {
var str strings.Builder
c.rserialize(root, &str)
return str.String()
}
func (c *Codec) rdeserialize(data *[]string) *TreeNode {
if (*data)[0] == "null" {
*data = (*data)[1:]
return nil
}
val, _ := strconv.Atoi((*data)[0])
root := &TreeNode{Val: val}
*data = (*data)[1:]
root.Left = c.rdeserialize(data)
root.Right = c.rdeserialize(data)
return root
}
func (c *Codec) deserialize(data string) *TreeNode {
dataArray := strings.Split(data, ",")
return c.rdeserialize(&dataArray)
}Explanation
Algorithm
Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы.
Пример:
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
👨💻
Алгоритм:
Сериализация дерева:
Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree.
Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None".
Пример:
Начните с корня, узел 1, строка сериализации становится "1,".
Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,".
Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None").
Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,").
Десериализация строки:
Разделите строку на список значений.
Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой.
😎