序列化和反序列化二叉树

Question

我正在研究 LeetCode 问题 297. Serialize and Deserialize Binary Tree:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

我从在 Geeks for Geeks 上找到的一个类似问题的正确解决方案中获得灵感：Serialize and Deserialize a Binary Tree :

class Tree 
{
    public void serialize(Node root, ArrayList<Integer> al) 
    {
        //code here
        if(root == null) {
            al.add(-1);
            return;
        }
        al.add(root.data);
        serialize(root.left,al);
        serialize(root.right,al);
    }
    

    public Node deSerialize(ArrayList<Integer> al)
    {
        //code here
        if(al.get(0) == -1) {
            al.remove(0);
            return null;
        }
        Node newNode = new Node(al.get(0));
        al.remove(0);
        newNode.left = deSerialize(al);
        newNode.right = deSerialize(al);
        return newNode;
    }
}

我尝试针对 LeetCode 问题调整此方法。但是，我的尝试没有产生所需的输出：

public class Codec {
    StringBuilder sb = new StringBuilder();
    public String serialize(TreeNode root) {
        if(root==null) {
            sb.append("^");
            return sb.toString();
        }
        sb.append(String.valueOf(root.val));
        serialize(root.left);
        serialize(root.right);
        return sb.toString();
    }
    public TreeNode deserialize(String data) {
        if(data.charAt(0)=='^') {
            data = data.substring(1);
            return null;
        }
        TreeNode newNode = new TreeNode(Character.getNumericValue(data.charAt(0)));
        data = data.substring(1);
        newNode.left = deserialize(data);
        newNode.right = deserialize(data);
        return newNode;
    }
}

我哪里错了？

Answer 1

一些备注：

Geeks-for-Geeks 问题有一个不同的接口：“序列化”被解释为将信息存储在数组（向量）中，而对于 LeetCode 问题，序列化是关于生成一个字符串.
您的代码有一个 sb 成员，可以在第二次调用 serialize 时重复使用。然而 serialize 的正确功能至少需要 sb 最初代表一个空字符串。
String.valueOf(root.val) 被追加，但是两个连续的字符串化值之间没有分隔符，所以 deserialize 不知道有多少位属于一个值。事实上，您的 deserialize 似乎假定每个数字仅由一位数字组成。这不能假设。
在deserialize中赋值data = data.substring(1)只会影响局部变量data，不会影响的data变量来电者。请注意 Geeks-for-Geeks 解决方案如何具有优势，它可以使用 array，它可以 mutate。字符串是不可变的，所以在 LeetCode 问题中我们不能使用这种策略。您可以通过使用第三个函数来解决这个问题，您将传递一个可变数组。

例如：

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "^";
        }
        return String.valueOf(root.val) + ","
             + serialize(root.left) + ","
             + serialize(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        return deserializeArray(new ArrayList<String>(Arrays.asList(data.split(","))));
    }
    
    private TreeNode deserializeArray(ArrayList<String> arr) {
        String value = arr.remove(0);
        if (value.charAt(0) == '^') {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(value));
        node.left = deserializeArray(arr);
        node.right = deserializeArray(arr);
        return node;
    }
}

序列化和反序列化二叉树

Serialize and Deserialize Binary Tree

java

serialization

tree

binary-tree

binary-search-tree