Hard

题目描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列化/反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示： 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：

输入：root = []
输出：[]

提示：

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

解题思路

这道题目要求我们设计二叉树的序列化和反序列化算法。主要有两种经典的解法：

解法一：前序遍历（推荐）

使用前序遍历进行序列化，遇到空节点时用特殊标记（如"null"）表示。序列化时按照"根-左-右"的顺序输出节点值，反序列化时也按照相同的顺序重建树结构。

序列化过程：递归遍历树，将节点值和空节点标记依次加入结果字符串。反序列化过程：使用队列或者索引来依次读取序列化字符串中的值，按照前序遍历的顺序重建树。

解法二：层序遍历

使用BFS层序遍历进行序列化，按层输出所有节点（包括空节点）。反序列化时也使用队列按层重建树结构。

前序遍历的优势在于序列化结果更紧凑（不需要输出叶子节点的空子节点），而且实现相对简单。因此推荐使用前序遍历解法。

核心思路是保证序列化和反序列化使用相同的遍历顺序，并正确处理空节点的情况。

代码实现

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string result;
        serializeHelper(root, result);
        return result;
    }
    
private:
    void serializeHelper(TreeNode* node, string& result) {
        if (node == nullptr) {
            result += "null,";
            return;
        }
        result += to_string(node->val) + ",";
        serializeHelper(node->left, result);
        serializeHelper(node->right, result);
    }
    
public:
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream iss(data);
        return deserializeHelper(iss);
    }
    
private:
    TreeNode* deserializeHelper(istringstream& iss) {
        string val;
        if (!getline(iss, val, ',') || val == "null") {
            return nullptr;
        }
        TreeNode* node = new TreeNode(stoi(val));
        node->left = deserializeHelper(iss);
        node->right = deserializeHelper(iss);
        return node;
    }
};

class Codec:

    def serialize(self, root):
        def preorder(node):
            if not node:
                vals.append("null")
                return
            vals.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
        
        vals = []
        preorder(root)
        return ",".join(vals)

    def deserialize(self, data):
        def build():
            val = next(vals)
            if val == "null":
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
        
        vals = iter(data.split(","))
        return build()

public class Codec {

    // Encodes a tree to a single string.
    public string serialize(TreeNode root) {
        var result = new List<string>();
        SerializeHelper(root, result);
        return string.Join(",", result);
    }
    
    private void SerializeHelper(TreeNode node, List<string> result) {
        if (node == null) {
            result.Add("null");
            return;
        }
        result.Add(node.val.ToString());
        SerializeHelper(node.left, result);
        SerializeHelper(node.right, result);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data) {
        var vals = new Queue<string>(data.Split(','));
        return DeserializeHelper(vals);
    }
    
    private TreeNode DeserializeHelper(Queue<string> vals) {
        if (vals.Count == 0) return null;
        string val = vals.Dequeue();
        if (val == "null") return null;
        
        TreeNode node = new TreeNode(int.Parse(val));
        node.left = DeserializeHelper(vals);
        node.right = DeserializeHelper(vals);
        return node;
    }
}

var serialize = function(root) {
    if (!root) return "null";
    return root.val + "," + serialize(root.left) + "," + serialize(root.right);
};

var deserialize = function(data) {
    const values = data.split(",");
    let index = 0;
    
    function buildTree() {
        if (values[index] === "null") {
            index++;
            return null;
        }
        
        const node = new TreeNode(parseInt(values[index]));
        index++;
        node.left = buildTree();
        node.right = buildTree();
        return node;
    }
    
    return buildTree();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
序列化O(n)O(n)
反序列化O(n)O(n)

其中 n 是二叉树中节点的数量。时间复杂度为 O(n) 是因为需要访问每个节点一次。空间复杂度为 O(n) 主要来自递归调用栈的深度（最坏情况下为 O(n)）和存储序列化结果的空间。

相关题目