serialization - 如何序列化二叉树

Question

我今天去参加了一次面试，面试官要求我序列化一棵二叉树。我实现了一种基于数组的方法，其中节点 i 的子节点(按级别顺序遍历编号)位于左子节点的 2*i 索引处，右子节点的子节点位于 2*i + 1 处。面试官看起来或多或少很高兴，但我想知道序列化到底意味着什么？它是否特别涉及展平树以写入磁盘，或者序列化树还包括将树转换为链表。另外，我们如何将树展平为(双向)链表，然后重建它？你能从链表中重新创建树的精确结构吗？

Answer 1

所有这些文章主要讨论序列化部分。反序列化部分一次性完成有点棘手。

我也实现了一个有效的反序列化解决方案。

问题:序列化和反序列化包含正数的二叉树。

序列化部分:

1. 使用 0 表示 null。
2. 使用前序遍历序列化为整数列表。

反序列化部分:

1. 接受整数列表并使用递归辅助方法进行反序列化。
2. 递归反序列化器返回一对(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;
    }
}