LeetCode 问题练习和总结：二叉树的序列化和反序列化 - 297 - 输入：根 = [1,2] 输出： 根[1,2] 提示

• 树中结点数在范围 [0, 10^4] 内
• -1000 <= Node.val <= 1000

二、解题思路

1. 序列化

• 使用前序遍历递归地将每个节点转换为字符串，如果节点为空，则用"null"表示。
• 使用逗号分隔每个节点值，形成完整的序列化字符串。

2. 反序列化

• 使用逗号分割序列化字符串，得到节点值的数组。
• 使用一个队列（或列表）来存储节点值，以便于在构建树时按顺序访问。
• 递归地构建树，每次从队列中取出一个值，如果值为"null"，则返回null表示空节点，否则创建一个新的节点，并递归构建其左右子树。

三、具体代码

import java.util.*;

// TreeNode 类现在是一个*类，不再嵌套在 Codec 类内部
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 "null,";
        // 前序遍历序列化
        return root.val + "," + serialize(root.left) + serialize(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserializeHelper(nodes);
    }

    private TreeNode deserializeHelper(Queue<String> nodes) {
        String val = nodes.poll();
        if ("null".equals(val)) return null;
        // 创建当前节点，并递归构建左右子树
        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = deserializeHelper(nodes);
        root.right = deserializeHelper(nodes);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

四、时间复杂度和空间复杂度

1. 时间复杂度

(1)serialize 方法

• serialize 方法采用前序遍历的方式来序列化二叉树。
• 对于树中的每个节点，我们都会进行一次访问。
• 时间复杂度是 O(n)，其中 n 是树中节点的数量。

(2)deserialize 方法

• deserialize 方法使用队列来反序列化字符串表示的树。
• 在反序列化过程中，我们同样需要访问每个节点一次。
• 时间复杂度也是 O(n)，因为每个节点都会被处理一次。

2. 空间复杂度

(1)serialize 方法

• serialize 方法递归地序列化树，递归栈的深度取决于树的高度。
• 在最坏的情况下（当树退化成一条链时），递归栈的深度为 n。
• 因此，空间复杂度是 O(n)，其中 n 是树的高度。

(2)deserialize 方法

• deserialize 方法使用了一个队列来存储序列化字符串分割后的字符串数组。
• 队列的大小最多是序列化字符串中逗号的数量加一，即 n + 1（每个节点后都有一个逗号，除了最后一个节点）。
• 因此，空间复杂度是 O(n)，其中 n 是树中节点的数量。

3. 总结

• 时间复杂度：O(n)，其中 n 是树中节点的数量。
• 空间复杂度：O(n)，其中 n 是树中节点的数量或树的高度，取决于具体是序列化还是反序列化操作。

这些分析假设了树是通过指针或引用连接的，并且不考虑字符串操作（如连接和分割）的具体实现细节，这些操作在最坏情况下的时间复杂度可能会影响总的时间复杂度。在实际应用中，字符串操作的时间复杂度可能会对性能有显著影响。

五、总结知识点