fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
东哥带你刷二叉树（序列化篇） :: labuladong的算法小抄
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))
/**
* 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));
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);
};
C++版（感觉就像再考字符串操作，查了一堆字符串string类的操作 :joy:
/**
* 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));
解题思路
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));
解题思路
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));
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
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
}
前序遍历+非递归的序列化+反序列化
记录一下反序列化使用前序+非递归方式的写法，这种反序列化时候的写法好像和二叉树中序非递归有点像
比较神奇，还没想通为什么前序序列化要用中序反序列化
class Codec {
public:
#define SEP ","
#define END "#"
#define MAX_STACK_SIZE 1000
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
// stack 空间预开辟
s.resize(MAX_STACK_SIZE);
// 栈顶指针
int top = 0;
// 根节点入栈
s[top++] = root;
TreeNode* node;
string res;
// 深度优先非递归(前序遍历)
while (top != 0){
node = s[--top];
if (node == nullptr)
{
res += END SEP;
continue;
}
res += to_string(node->val) + SEP;
s[top++] = node->right;
s[top++] = node->left;
}
return res;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
// stack 空间预开辟
s.resize(MAX_STACK_SIZE);
int top = 0;
// 分割字符串
stringstream fin(data);
string item;
vector<TreeNode*> preorder;
while(getline(fin, item, SEP[0]))
{
if (item.compare(END) == 0)
{
preorder.emplace_back(nullptr);
continue;
}
TreeNode* tmp = new TreeNode(stoi(item));
preorder.emplace_back(tmp);
}
int i = 0;
// 根节点
TreeNode* pre = preorder[i++];
while(top != 0 || pre != nullptr){
// 按照前序排列，先构造左子树直到左子树遍历到叶子
if (pre != nullptr) {
s[top++] = pre;
pre->left = preorder[i++];
pre = pre->left;
}
// 回退之后从下向上简历右子树
else {
pre = s[--top];
pre->right = preorder[i++];
pre = pre->right;
}
}
return preorder[0];
}
// 用vector模拟stack，避免动态开辟空间
vector<TreeNode*> s;
};
