今天我参加了一场面试，被要求序列化二叉树。我采用了基于数组的方法，其中节点i（按层次遍历编号）的子节点在2*i位置处为左子节点，2*i+1位置处为右子节点。面试官似乎对此表示满意，但我想知道序列化的确切含义是什么？它是否特指将树压缩成可写入磁盘的形式，或者序列化树是否也包括只将树转化为链表呢？此外，我们如何将树压缩成（双向）链表，然后重构它？你能从链表中重新创建出与原树完全相同的结构吗？
如何对二叉树进行序列化
33
- worker1138
3
相关链接：https://dev59.com/1HE85IYBdhLWcg3wpFOu - Aryabhatta
大多数情况下，面试官会问这个问题，以查看您是否会使用递归方法。基本上，您为叶节点编写序列化，然后对于父节点，调用serialize(left)，输出当前节点，serialize(right)。这是一种优雅的解决方案，让面试官知道您已经学过不错的算法课程。 - Zeki
感谢大家提供的有用信息。 - worker1138
11个回答
13
所有这些文章大多数都谈论序列化部分，反序列化部分稍微有点棘手，需要在一次遍历中完成。
我已经实现了一个高效的反序列化解决方案。
问题：对包含正整数的二叉树进行序列化和反序列化。
序列化部分：
- 使用0表示null。
- 使用先序遍历将其序列化为整数列表。
反序列化部分：
- 接收整数列表并使用递归辅助方法进行反序列化。
- 递归反序列化器返回一对（BTNode节点，int nextIndexToRead），其中node是到目前为止构建的树节点，nextIndexToRead是下一个要读取的数字在序列化数字列表中的位置。
以下是Java代码：
public final class BinaryTreeSerializer
{
public static List<Integer> Serialize(BTNode root)
{
List<Integer> serializedNums = new ArrayList<Integer>();
SerializeRecursively(root, serializedNums);
return serializedNums;
}
private static void SerializeRecursively(BTNode node, List<Integer> nums)
{
if (node == null)
{
nums.add(0);
return;
}
nums.add(node.data);
SerializeRecursively(node.left, nums);
SerializeRecursively(node.right, nums);
}
public static BTNode Deserialize(List<Integer> serializedNums)
{
Pair pair = DeserializeRecursively(serializedNums, 0);
return pair.node;
}
private static Pair DeserializeRecursively(List<Integer> serializedNums, int start)
{
int num = serializedNums.get(start);
if (num == 0)
{
return new Pair(null, start + 1);
}
BTNode node = new BTNode(num);
Pair p1 = DeserializeRecursively(serializedNums, start + 1);
node.left = p1.node;
Pair p2 = DeserializeRecursively(serializedNums, p1.startIndex);
node.right = p2.node;
return new Pair(node, p2.startIndex);
}
private static final class Pair
{
BTNode node;
int startIndex;
private Pair(BTNode node, int index)
{
this.node = node;
this.startIndex = index;
}
}
}
public class BTNode
{
public int data;
public BTNode left;
public BTNode right;
public BTNode(int data)
{
this.data = data;
}
}
- AbhishekPrateek
9
使用先序遍历，将二叉树序列化。 使用相同的先序遍历反序列化树。注意边缘情况。这里用"#"表示 null 节点。
public static String serialize(TreeNode root){
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
private static void serialize(TreeNode node, StringBuilder sb){
if (node == null) {
sb.append("# ");
} else {
sb.append(node.val + " ");
serialize(node.left, sb);
serialize(node.right, sb);
}
}
public static TreeNode deserialize(String s){
if (s == null || s.length() == 0) return null;
StringTokenizer st = new StringTokenizer(s, " ");
return deserialize(st);
}
private static TreeNode deserialize(StringTokenizer st){
if (!st.hasMoreTokens())
return null;
String val = st.nextToken();
if (val.equals("#"))
return null;
TreeNode root = new TreeNode(Integer.parseInt(val));
root.left = deserialize(st);
root.right = deserialize(st);
return root;
}
- sreeprasad
7
方法一： 对树数据进行中序遍历和前序遍历，以序列化数据。 在反序列化时使用前序遍历，并在中序遍历上进行BST，以正确构建树。
需要两种遍历方式，因为A->B->C可以表示为前序，即使结构不同也是如此。
方法二： 在左或右子节点为空的位置使用#作为哨兵。
- Ketan Thakkar
1
我一直在努力理解它的要点。这里是我的Java实现。如上所述，这是一个二叉树而不是BST。对于序列化，先序遍历似乎更容易（将空节点转换为“NULL”字符串）。请检查下面的代码，其中包括递归调用的完整示例。对于反序列化，该字符串被转换为LinkedList，其中remove（0）以O（1）运行时间获取顶部元素。请在代码注释中查看反序列化的完整示例。希望这能帮助某些人比我少挣扎：） 每种方法（序列化和反序列化）的总运行时间都是二叉树遍历的相同运行时间，即O（n），其中n是树中节点（条目）的数量
import java.util.LinkedList;
import java.util.List;
public class SerDesBinTree<T> {
public static class TreeEntry<T>{
T element;
TreeEntry<T> left;
TreeEntry<T> right;
public TreeEntry(T x){
element = x;
left = null;
right = null;
}
}
TreeEntry<T> root;
int size;
StringBuilder serSB = new StringBuilder();
List<String> desList = new LinkedList<>();
public SerDesBinTree(){
root = null;
size = 0;
}
public void traverseInOrder(){
traverseInOrder(this.root);
}
public void traverseInOrder(TreeEntry<T> node){
if (node != null){
traverseInOrder(node.left);
System.out.println(node.element);
traverseInOrder(node.right);
}
}
public void serialize(){
serialize(this.root);
}
/*
* 1
* / \
* 2 3
* /
* 4
*
* ser(1)
* serSB.append(1) serSB: 1
* ser(1.left)
* ser(1.right)
* |
* |
* ser(1.left=2)
* serSB.append(2) serSB: 1, 2
* ser(2.left)
* ser(2.right)
* |
* |
* ser(2.left=null)
* serSB.append(NULL) serSB: 1, 2, NULL
* return
* |
* ser(2.right=null)
* serSB.append(NULL) serSB: 1, 2, NULL, NULL
* return
*
* |
* ser(1.right=3)
* serSB.append(3) serSB: 1, 2, NULL, NULL, 3
* ser(3.left)
* ser(3.right)
*
* |
* ser(3.left=4)
* serSB.append(4) serSB: 1, 2, NULL, NULL, 3, 4
* ser(4.left)
* ser(4.right)
*
* |
* ser(4.left=null)
* serSB.append(NULL) serSB: 1, 2, NULL, NULL, 3, 4, NULL
* return
*
* ser(4.right=null)
* serSB.append(NULL) serSB: 1, 2, NULL, NULL, 3, 4, NULL, NULL
* return
*
* ser(3.right=null)
* serSB.append(NULL) serSB: 1, 2, NULL, NULL, 3, 4, NULL, NULL, NULL
* return
*
*/
public void serialize(TreeEntry<T> node){
// preorder traversal to build the string
// in addition: NULL will be added (to make deserialize easy)
// using StringBuilder to append O(1) as opposed to
// String which is immutable O(n)
if (node == null){
serSB.append("NULL,");
return;
}
serSB.append(node.element + ",");
serialize(node.left);
serialize(node.right);
}
public TreeEntry<T> deserialize(TreeEntry<T> newRoot){
// convert the StringBuilder into a list
// so we can do list.remove() for the first element in O(1) time
String[] desArr = serSB.toString().split(",");
for (String s : desArr){
desList.add(s);
}
return deserialize(newRoot, desList);
}
/*
* 1
* / \
* 2 3
* /
* 4
*
* deser(root, list) list: 1, 2, NULL, NULL, 3, 4, NULL, NULL, NULL
* root = new TreeEntry(1) list: 2, NULL, NULL, 3, 4, NULL, NULL, NULL
* root.left = deser(root.left, list) // **
* root.right = deser(root.right, list) // *-*
* return root // ^*^
*
*
* so far subtree
* 1
* / \
* null null
*
* deser(root.left, list)
* root.left = new TreeEntry(2) list: NULL, NULL, 3, 4, NULL, NULL, NULL
* root.left.left = deser(root.left.left, list) // ***
* root.left.right = deser(root.left.right, list) // ****
* return root.left // eventually return new TreeEntry(2) to ** above after the two calls are done
*
* so far subtree
* 2
* / \
* null null
*
* deser(root.left.left, list)
* // won't go further down as the next in list is NULL
* return null // to *** list: NULL, 3, 4, NULL, NULL, NULL
*
* so far subtree (same, just replacing null)
* 2
* / \
* null null
*
* deser(root.left.right, list)
* // won't go further down as the next in list is NULL
* return null // to **** list: 3, 4, NULL, NULL, NULL
*
* so far subtree (same, just replacing null)
* 2
* / \
* null null
*
*
* so far subtree // as node 2 completely returns to ** above
* 1
* / \
* 2 null
* / \
* null null
*
*
* deser(root.right, list)
* root.right = new TreeEntry(3) list: 4, NULL, NULL, NULL
* root.right.left = deser(root.right.left, list) // *&*
* root.right.right = deser(root.right.right, list) // *---*
* return root.right // eventually return to *-* above after the previous two calls are done
*
* so far subtree
* 3
* / \
* null null
*
*
* deser(root.right.left, list)
* root.right.left = new TreeEntry(4) list: NULL, NULL, NULL
* root.right.left.left = deser(root.right.left.left, list) // *(*
* root.right.left.right = deser(root.right.left.right, list) // *)*
* return root.right.left // to *&*
*
* so far subtree
* 4
* / \
* null null
*
* deser(root.right.left.left, list)
* // won't go further down as the next in list is NULL
* return null // to *(* list: NULL, NULL
*
* so far subtree (same, just replacing null)
* 4
* / \
* null null
*
* deser(root.right.left.right, list)
* // won't go further down as the next in list is NULL
* return null // to *)* list: NULL
*
*
* so far subtree (same, just replacing null)
* 4
* / \
* null null
*
*
* so far subtree
* 3
* / \
* 4 null
* / \
* null null
*
*
* deser(root.right.right, list)
* // won't go further down as the next in list is NULL
* return null // to *---* list: empty
*
* so far subtree (same, just replacing null of the 3 right)
* 3
* / \
* 4 null
* / \
* null null
*
*
* now returning the subtree rooted at 3 to root.right in *-*
*
* 1
* / \
* / \
* / \
* 2 3
* / \ / \
* null null / null
* /
* 4
* / \
* null null
*
*
* finally, return root (the tree rooted at 1) // see ^*^ above
*
*/
public TreeEntry<T> deserialize(TreeEntry<T> node, List<String> desList){
if (desList.size() == 0){
return null;
}
String s = desList.remove(0); // efficient operation O(1)
if (s.equals("NULL")){
return null;
}
Integer sInt = Integer.parseInt(s);
node = new TreeEntry<T>((T)sInt);
node.left = deserialize(node.left, desList);
node.right = deserialize(node.right, desList);
return node;
}
public static void main(String[] args) {
/*
* 1
* / \
* 2 3
* /
* 4
*
*/
SerDesBinTree<Integer> tree = new SerDesBinTree<>();
tree.root = new TreeEntry<Integer>(1);
tree.root.left = new TreeEntry<Integer>(2);
tree.root.right = new TreeEntry<Integer>(3);
tree.root.right.left = new TreeEntry<Integer>(4);
//tree.traverseInOrder();
tree.serialize();
//System.out.println(tree.serSB);
tree.root = null;
//tree.traverseInOrder();
tree.root = tree.deserialize(tree.root);
//tree.traverseInOrder();
// deserialize into a new tree
SerDesBinTree<Integer> newTree = new SerDesBinTree<>();
newTree.root = tree.deserialize(newTree.root);
newTree.traverseInOrder();
}
}
- Khaled Alnaami
0
序列化和反序列化二叉树：
public class BTSerialization {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
// 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("()");
return;
}
sb.append('(').append(root.val);
serialize(root.left, sb);
serialize(root.right, sb);
sb.append(')');
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if ("()".equals(data)) return null;
data = data.substring(1, data.length() - 1); // Unwrap the two parenthesis (root(left)(right))
int i = 0;
while (data.charAt(i) != '(') i++;
TreeNode root = new TreeNode(Integer.parseInt(data.substring(0, i)));
data = data.substring(i);
i = -1;
int open = 0;
while (true) { // Find left child- starts with parenthesis
i++;
if (data.charAt(i) == '(') open++;
else if (data.charAt(i) == ')') {
open--;
if (open == 0) break;
}
}
root.left = deserialize(data.substring(0, i + 1));
data = data.substring(i + 1); // The rest is right child- starts with parenthesis
root.right = deserialize(data);
return root;
}
public static void main(String[] args) {
BTSerialization b = new BTSerialization();
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
node1.left = node2;
node1.right = node3;
node3.left = node4;
node3.right = node5;
TreeNode root = b.deserialize(b.serialize(node1));
System.out.println();
}
}
序列化和反序列化 N 叉树： 使用此代码，您可以序列化、反序列化任何 N 叉树。基本上，二叉树是一种 2 叉树。N 表示整个树中所有节点的最大子节点数。
public class CodecNry {
class Node {
public int val;
public List<Node> children;
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
public String serialize(Node root) {
if (root == null) return ""; // Serialization base case
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(root.val).append(",").append(root.children.size()); // Add root val+,+num of children
for (Node child : root.children)
stringBuilder.append(",").append(serialize(child)); // Add children recursively, one by one
return stringBuilder.toString(); // Return result
}
int i;
public Node deserialize(String data) {
if (data.isBlank()) return null; // Base case root is null
i = 0; // The index on the tokens
return recursiveDeserialize(data.split(",")); // Recursively build the tree from the tokenized string
}
private Node recursiveDeserialize(String[] nums) {
if (i == nums.length) return null; // Base case- no more child
Node root = new Node(Integer.parseInt(nums[i++]), new ArrayList<>()); // Build the root
int childrenCount = Integer.parseInt(nums[i++]); // Get number of children
for (int j = 0; j < childrenCount; j++) { // Add children recursively one by one
Node child = recursiveDeserialize(nums);
if (child != null) root.children.add(child); // If child is not null, add it to the children of root
}
return root; // Return the root of the tree
}
}
- Mohammad
0
如何执行中序遍历，并将根键和所有节点键放入 std::list 或其他容器（您可以选择）中，从而使树变为扁平化。然后，使用 boost 库简单地对 std::list 或您选择的容器进行序列化。
相反地，通过标准插入到二叉树来简单地重建树。对于非常大的树来说，这可能不是完全高效的，但将树转换为 std::list 的运行时间最多为 O(n)，重新构建树的运行时间最多为 O(log n)。
正如我所提到的，我即将在 C++ 中将我的数据库从 Java 转换为 C++，并且我打算使用此方法对我刚刚编写的树进行序列化。
相反地，通过标准插入到二叉树来简单地重建树。对于非常大的树来说，这可能不是完全高效的，但将树转换为 std::list 的运行时间最多为 O(n)，重新构建树的运行时间最多为 O(log n)。
正如我所提到的，我即将在 C++ 中将我的数据库从 Java 转换为 C++，并且我打算使用此方法对我刚刚编写的树进行序列化。
- user633658
2
1一个二叉树不一定是二叉搜索树，因此它可能没有排序。（考虑二进制空间分割。） - idbrii
@idbrii 但是树并不需要被排序。中序遍历保持了顺序并将树扁平化以进行序列化。从序列化后的扁平列表中插入到二叉树中会返回一个具有相同顺序的新二叉树。排序与此无关。 - user633658
0
最好的方式是使用特殊字符（如前面评论所提到的＃）作为哨兵。这比构造中序遍历数组和前/后序遍历数组来说，在时间和空间复杂度上都更好。而且，实现起来也更加容易。
链表在这里不是一个好选择，因为为了重建树，你最好有恒定的元素访问时间。
- Haitao
1
如果树节点的值可以是“＃”呢？ - Skiptomylu
0
将其转换为大小为(2n + 1)的数组 每个左儿子和右儿子将分别在节点编号的(2 * node number)和((2 * node number) + 1)的位置上。
- Eliko
0
这是一份Python中的晚期答案。它使用(深度优先)前序序列化并返回一个
字符串列表。反序列化将返回树形结构。class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
# This method serializes the tree into a string
def serialize(root):
vals = []
def encode(node):
vals.append(str(node.val))
if node.left is not None:
encode(node.left)
else:
vals.append("L")
if node.right is not None:
encode(node.right)
else:
vals.append("R")
encode(root)
print(vals)
return vals
# This method deserializes the string back into the tree
def deserialize(string_list):
def create_a_tree(sub_list):
if sub_list[0] == 'L' or sub_list[0] == 'R':
del sub_list[0]
return None
parent = Node(sub_list[0])
del sub_list[0]
parent.left = create_a_tree(sub_list)
parent.right = create_a_tree(sub_list)
return parent
if len(string_list) != 0:
root_node = create_a_tree(string_list)
else:
print("ERROR - empty string!")
return 0
return root_node
测试：
tree1 = Node('root', Node('left'), Node('right'))
t = deserialize(serialize(tree1))
print(str(t.right.val))
- Bn.F76
0
我没有使用先序遍历，而是使用BFS。这是来自leetcode的一个问题。
当使用先序遍历时，大多数人的实现都是不正确的：期望的结果应该是
"[1,2,3,null,null,4,5]"，但是大多数人打印输出为"[1,2,3,null,null,4,5,null,null]"，因为他们没有计算层级。
这是我的实现，可以得到正确的结果。
class Node(object):
def __init__(self,data):
self.left = None
self.right = None
self.data = data
def serialize(root):
queue = [(root,0)]
result = []
max_level_with_value = 0
while queue:
(node,l) = queue.pop(0)
if node:
result.append((node.data,l))
queue.extend([(node.left,l+1),
(node.right,l+1)
])
max_level_with_value = max(max_level_with_value,l)
else:
result.append(('null',l))
filter_redundant(result,max_level_with_value)
def filter_redundant(result,max_level_with_value):
for v,l in result:
if l<= max_level_with_value:
print(v)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(5)
serialize(root)
- Mike
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接