class Solution:
def preorder(self, root: TreeNode):
if not root: return []
return [str(root.val)] +self. preorder(root.left) + self.preorder(root.right)
def inorder(self, root: TreeNode):
if not root: return []
return self.inorder(root.left) + [str(root.val)] + self.inorder(root.right)
def serialize(self, root):
ans = ''
ans += ','.join(self.preorder(root))
ans += '$'
ans += ','.join(self.inorder(root))
return ans
反序列化:
这里我直接用了力扣 105. 从前序与中序遍历序列构造二叉树 的解法,一行代码都不改。
class Solution:
def deserialize(self, data: str):
preorder, inorder = data.split('$')
if not preorder: return None
return self.buildTree(preorder.split(','), inorder.split(','))
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# 实际上inorder 和 preorder 一定是同时为空的,因此你无论判断哪个都行
if not preorder:
return None
root = TreeNode(preorder[0])
i = inorder.index(root.val)
root.left = self.buildTree(preorder[1:i + 1], inorder[:i])
root.right = self.buildTree(preorder[i + 1:], inorder[i+1:])
return root
class Codec:
def serialize_dfs(self, root, ans):
# 空节点也需要序列化,否则无法唯一确定一棵树,后不赘述。
if not root: return ans + '#,'
# 节点之间通过逗号(,)分割
ans += str(root.val) + ','
ans = self.serialize_dfs(root.left, ans)
ans = self.serialize_dfs(root.right, ans)
return ans
def serialize(self, root):
# 由于最后会添加一个额外的逗号,因此需要去除最后一个字符,后不赘述。
return self.serialize_dfs(root, '')[:-1]
Java 代码:
public class Codec {
public String serialize_dfs(TreeNode root, String str) {
if (root == null) {
str += "None,";
} else {
str += str.valueOf(root.val) + ",";
str = serialize_dfs(root.left, str);
str = serialize_dfs(root.right, str);
}
return str;
}
public String serialize(TreeNode root) {
return serialize_dfs(root, "");
}
}