Medium

题目描述

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

设计一个算法来序列化和反序列化二叉搜索树。对序列化/反序列化算法应该如何工作没有限制。你需要确保二叉搜索树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。

编码的字符串应该尽可能紧凑。

示例 1:

输入: root = [2,1,3]
输出: [2,1,3]

示例 2:

输入: root = []
输出: []

约束条件:

  • 树中节点数的范围是 [0, 10^4]
  • 0 <= Node.val <= 10^4
  • 输入的树保证是二叉搜索树

解题思路

本题要求序列化和反序列化二叉搜索树，关键是利用BST的性质来优化存储。

核心思路： 由于BST具有中序遍历有序的特性，我们可以只存储前序遍历的结果，在反序列化时利用BST性质重建树结构。

方法一：前序遍历 + 递归重建（推荐）

  • 序列化：使用前序遍历将节点值存储为逗号分隔的字符串
  • 反序列化：根据前序遍历结果和BST性质递归重建。对于当前节点，所有小于当前值的节点在左子树，大于当前值的节点在右子树

方法二：前序遍历 + 栈重建 使用栈来模拟递归过程，维护当前节点的取值范围来判断左右子树的归属。

优化点： 相比通用的二叉树序列化（需要存储null标记），BST只需存储节点值，大大减少了存储空间，实现了题目要求的"尽可能紧凑"。

时间复杂度：序列化和反序列化都是O(n)，空间复杂度O(n)。

代码实现

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string result;
        preorder(root, result);
        return result;
    }
    
private:
    void preorder(TreeNode* root, string& result) {
        if (!root) return;
        result += to_string(root->val) + ",";
        preorder(root->left, result);
        preorder(root->right, result);
    }
    
public:
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        
        vector<int> vals;
        stringstream ss(data);
        string val;
        while (getline(ss, val, ',')) {
            if (!val.empty()) {
                vals.push_back(stoi(val));
            }
        }
        
        int idx = 0;
        return build(vals, idx, INT_MIN, INT_MAX);
    }
    
private:
    TreeNode* build(vector<int>& vals, int& idx, int minVal, int maxVal) {
        if (idx >= vals.size() || vals[idx] < minVal || vals[idx] > maxVal) {
            return nullptr;
        }
        
        int val = vals[idx++];
        TreeNode* root = new TreeNode(val);
        root->left = build(vals, idx, minVal, val);
        root->right = build(vals, idx, val, maxVal);
        return root;
    }
};

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string."""
        vals = []
        
        def preorder(node):
            if node:
                vals.append(str(node.val))
                preorder(node.left)
                preorder(node.right)
        
        preorder(root)
        return ','.join(vals)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree."""
        if not data:
            return None
        
        vals = list(map(int, data.split(',')))
        self.idx = 0
        
        def build(min_val, max_val):
            if self.idx >= len(vals) or vals[self.idx] < min_val or vals[self.idx] > max_val:
                return None
            
            val = vals[self.idx]
            self.idx += 1
            root = TreeNode(val)
            root.left = build(min_val, val)
            root.right = build(val, max_val)
            return root
        
        return build(float('-inf'), float('inf'))

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

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data) {
        if (string.IsNullOrEmpty(data)) return null;
        
        string[] parts = data.Split(',');
        List<int> vals = new List<int>();
        foreach (string part in parts) {
            if (!string.IsNullOrEmpty(part)) {
                vals.Add(int.Parse(part));
            }
        }
        
        int idx = 0;
        return Build(vals, ref idx, int.MinValue, int.MaxValue);
    }
    
    private TreeNode Build(List<int> vals, ref int idx, int minVal, int maxVal) {
        if (idx >= vals.Count || vals[idx] < minVal || vals[idx] > maxVal) {
            return null;
        }
        
        int val = vals[idx++];
        TreeNode root = new TreeNode(val);
        root.left = Build(vals, ref idx, minVal, val);
        root.right = Build(vals, ref idx, val, maxVal);
        return root;
    }
}

var serialize = function(root) {
    const vals = [];
    
    function preorder(node) {
        if (node) {
            vals.push(node.val);
            preorder(node.left);
            preorder(node.right);
        }
    }
    
    preorder(root);
    return vals.join(',');
};

var deserialize = function(data) {
    if (!data) return null;
    
    const vals = data.split(',').map(Number);
    let idx = 0;
    
    function build(minVal, maxVal) {
        if (idx >= vals.length || vals[idx] < minVal || vals[idx] > maxVal) {
            return null;
        }
        
        const val = vals[idx++];
        const root = new TreeNode(val);
        root.left = build(minVal, val);
        root.right = build(val, maxVal);
        return root;
    }
    
    return build(-Infinity, Infinity);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
序列化O(n)O(n)
反序列化O(n)O(n)

其中 n 为二叉搜索树的节点数量。序列化需要遍历所有节点，反序列化需要重建所有节点，空间复杂度主要来自存储序列化字符串和递归调用栈。

相关题目