449.序列化和反序列化二叉搜索树
链接：449.序列化和反序列化二叉搜索树
难度：Medium
标签：树、深度优先搜索、广度优先搜索、设计、二叉搜索树、字符串、二叉树
简介：给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。 。
题解 1 - python
- 编辑时间：2023-09-04
- 执行用时：248ms
- 内存消耗：19.74MB
- 编程语言：python
- 解法介绍：同上。
class Codec:
def serialize(self, node: Optional[TreeNode]) -> str:
"""Encodes a tree to a single string.
"""
if not node:
return "N"
return f"{node.val},({self.serialize(node.left)}),({self.serialize(node.right)})"
def deserialize(self, s: str) -> Optional[TreeNode]:
"""Decodes your encoded data to tree.
"""
if s == "N":
return None
s1 = s2 = s3 = ''
split_idx = -1
level = 0
for i in range(len(s)):
if s[i] == '(':
level += 1
elif s[i] == ')':
level -= 1
elif s[i] == ',' and level == 0:
if split_idx == -1:
s1 = s[:i]
split_idx = i + 1
else:
s2 = s[split_idx + 1:i - 1]
s3 = s[i + 2:-1]
return TreeNode(int(s1), self.deserialize(s2), self.deserialize(s3))
题解 2 - typescript
- 编辑时间：2021-08-14
- 执行用时：108ms
- 内存消耗：46.1MB
- 编程语言：typescript
- 解法介绍：JSON 序列化。
function serialize(root: TreeNode | null): string {
return JSON.stringify(root);
}
function deserialize(data: string): TreeNode | null {
return JSON.parse(data);
}
题解 3 - python
- 编辑时间：2023-09-04
- 执行用时：248ms
- 内存消耗：19.74MB
- 编程语言：python
- 解法介绍：同上。
class Codec:
def serialize(self, node: Optional[TreeNode]) -> str:
"""Encodes a tree to a single string.
"""
if not node:
return "N"
return f"{node.val},({self.serialize(node.left)}),({self.serialize(node.right)})"
def deserialize(self, s: str) -> Optional[TreeNode]:
"""Decodes your encoded data to tree.
"""
if s == "N":
return None
s1 = s2 = s3 = ''
split_idx = -1
level = 0
for i in range(len(s)):
if s[i] == '(':
level += 1
elif s[i] == ')':
level -= 1
elif s[i] == ',' and level == 0:
if split_idx == -1:
s1 = s[:i]
split_idx = i + 1
else:
s2 = s[split_idx + 1:i - 1]
s3 = s[i + 2:-1]
return TreeNode(int(s1), self.deserialize(s2), self.deserialize(s3))
题解 4 - python
- 编辑时间：2023-09-04
- 执行用时：248ms
- 内存消耗：19.74MB
- 编程语言：python
- 解法介绍：同上。
class Codec:
def serialize(self, node: Optional[TreeNode]) -> str:
"""Encodes a tree to a single string.
"""
if not node:
return "N"
return f"{node.val},({self.serialize(node.left)}),({self.serialize(node.right)})"
def deserialize(self, s: str) -> Optional[TreeNode]:
"""Decodes your encoded data to tree.
"""
if s == "N":
return None
s1 = s2 = s3 = ''
split_idx = -1
level = 0
for i in range(len(s)):
if s[i] == '(':
level += 1
elif s[i] == ')':
level -= 1
elif s[i] == ',' and level == 0:
if split_idx == -1:
s1 = s[:i]
split_idx = i + 1
else:
s2 = s[split_idx + 1:i - 1]
s3 = s[i + 2:-1]
return TreeNode(int(s1), self.deserialize(s2), self.deserialize(s3))
题解 5 - cpp
- 编辑时间：2022-05-11
- 执行用时：64ms
- 内存消耗：45.7MB
- 编程语言：cpp
- 解法介绍：递归。
class Codec {
public:
string serialize(TreeNode *root) {
if (root == nullptr) return "(-1)";
return "(" + to_string(root->val) + "," + serialize(root->left) + "," +
serialize(root->right) + ")";
}
TreeNode *deserialize(string data) {
if (data == "(-1)") return nullptr;
string l, r;
int val = analysis(data, l, r);
TreeNode *ans = new TreeNode(val);
ans->left = deserialize(l);
ans->right = deserialize(r);
return ans;
}
int analysis(string &data, string &l, string &r) {
int level = 0, n = data.size(), val;
int i = 0, prev = 1, cnt = 0;
for (; i < n; i++) {
int ch = data[i];
if (ch == '(') {
level++;
} else if (ch == ')') {
level--;
} else if (ch == ',' && level == 1) {
string substr = data.substr(prev, i - prev);
if (cnt == 0)
val = stoi(substr);
else if (cnt == 1)
l = substr;
cnt++;
prev = i + 1;
}
}
r = data.substr(prev, i - prev - 1);
return val;
}
};
题解 6 - python
- 编辑时间：2023-09-04
- 执行用时：248ms
- 内存消耗：19.74MB
- 编程语言：python
- 解法介绍：同上。
class Codec:
def serialize(self, node: Optional[TreeNode]) -> str:
"""Encodes a tree to a single string.
"""
if not node:
return "N"
return f"{node.val},({self.serialize(node.left)}),({self.serialize(node.right)})"
def deserialize(self, s: str) -> Optional[TreeNode]:
"""Decodes your encoded data to tree.
"""
if s == "N":
return None
s1 = s2 = s3 = ''
split_idx = -1
level = 0
for i in range(len(s)):
if s[i] == '(':
level += 1
elif s[i] == ')':
level -= 1
elif s[i] == ',' and level == 0:
if split_idx == -1:
s1 = s[:i]
split_idx = i + 1
else:
s2 = s[split_idx + 1:i - 1]
s3 = s[i + 2:-1]
return TreeNode(int(s1), self.deserialize(s2), self.deserialize(s3))
题解 7 - python
- 编辑时间：2023-09-04
- 执行用时：248ms
- 内存消耗：19.74MB
- 编程语言：python
- 解法介绍：同上。
class Codec:
def serialize(self, node: Optional[TreeNode]) -> str:
"""Encodes a tree to a single string.
"""
if not node:
return "N"
return f"{node.val},({self.serialize(node.left)}),({self.serialize(node.right)})"
def deserialize(self, s: str) -> Optional[TreeNode]:
"""Decodes your encoded data to tree.
"""
if s == "N":
return None
s1 = s2 = s3 = ''
split_idx = -1
level = 0
for i in range(len(s)):
if s[i] == '(':
level += 1
elif s[i] == ')':
level -= 1
elif s[i] == ',' and level == 0:
if split_idx == -1:
s1 = s[:i]
split_idx = i + 1
else:
s2 = s[split_idx + 1:i - 1]
s3 = s[i + 2:-1]
return TreeNode(int(s1), self.deserialize(s2), self.deserialize(s3))