logo标签列表

如何对二叉树进行序列化

serializationtreebinary-treeflattenbinary-search-tree
33

今天我参加了一场面试，被要求序列化二叉树。我采用了基于数组的方法，其中节点i（按层次遍历编号）的子节点在2*i位置处为左子节点，2*i+1位置处为右子节点。面试官似乎对此表示满意，但我想知道序列化的确切含义是什么？它是否特指将树压缩成可写入磁盘的形式，或者序列化树是否也包括只将树转化为链表呢？此外，我们如何将树压缩成（双向）链表，然后重构它？你能从链表中重新创建出与原树完全相同的结构吗？

相关链接：https://dev59.com/1HE85IYBdhLWcg3wpFOu - Aryabhatta
大多数情况下，面试官会问这个问题，以查看您是否会使用递归方法。基本上，您为叶节点编写序列化，然后对于父节点，调用serialize(left)，输出当前节点，serialize(right)。这是一种优雅的解决方案，让面试官知道您已经学过不错的算法课程。 - Zeki
感谢大家提供的有用信息。 - worker1138
11个回答
-2

序列化是将数据结构或对象转换为一系列位的过程，以便可以将其存储在文件或内存缓冲区中，或通过网络连接链路传输到同一计算机环境或另一个计算机环境中以便稍后重建。

反序列化是将字符串转换回原始树结构的过程。

序列化和反序列化的概念与编译器对代码所做的操作非常相似。整个编译过程中有多个阶段，但我们将尝试保持抽象。

给定一段代码，编译器将不同的明确定义的组件分解为标记（例如，int是一个标记，double是另一个标记，{是一个标记，}是另一个标记等）。 [演示抽象级别的编译的链接][1]。

序列化：我们使用先序遍历逻辑将树序列化为字符串。 我们将添加“X”来表示树中的空指针/节点。 此外，为了记住我们的反序列化逻辑，我们需要在每个序列化的节点值后添加“,”，以便反序列化过程可以访问每个使用“,”分隔的节点值。

Leetcode链接：https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Back To Back SWE Youtube频道的解释: https://www.youtube.com/watch?v=suj1ro8TIVY

For example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,null,null,3,4,null,null,5,null,null,]"

 /**
 * 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.
    public String serialize(TreeNode root) {

        if(root == null)
            return "X,";

        String leftSerialized = serialize(root.left);
        String rightSerialized = serialize(root.right);

        return root.val + "," + leftSerialized + rightSerialized;
    }

    private TreeNode deserializeHelper(Queue<String> queue)
    {
        String nodeValue = queue.poll();

        if(nodeValue.equals("X"))
            return null;

        TreeNode newNode = new TreeNode(Integer.valueOf(nodeValue));

        newNode.left = deserializeHelper(queue);
        newNode.right = deserializeHelper(queue);

        return newNode;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        Queue<String> queue = new LinkedList<>();
        queue.addAll(Arrays.asList(data.split(",")));

        return deserializeHelper(queue);
    }
}

//Codec object will be instantiated and called as such:
//Codec codec = new Codec();
//codec.deserialize(codec.serialize(root));
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接