1.题目基本信息

1.1.题目描述

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

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

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

1.2.题目地址

https://leetcode.cn/problems/serialize-and-deserialize-bst/description/

2.解题方法

2.1.解题思路

思路1: 带None结点的前序遍历（二叉树通用）

思路2: 不带None节点的前序遍历（适用于二叉搜索树）

3.解题代码

python代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# 思路2：构建二叉树不带None结点的前序序列，利用二叉树有序的特点进行递归创建
class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        node = root
        stack = []
        result = ""
        while node or stack:
            while node:
                result += f"{node.val},"
                stack.append(node)
                node = node.left
            node = stack.pop()
            node = node.right
        return result
        
    def deserialize(self, data: str) -> Optional[TreeNode]:
        arr = []
        nodeStr = ""
        for i in range(len(data)):
            if data[i] == ",":
                arr.append(int(nodeStr))
                nodeStr = ""
            else:
                nodeStr += data[i]
        def dfs(left:int, right:int) -> TreeNode:
            if right < left:
                return None
            val = arr[left]
            node = TreeNode(val)
            # arr[left+1:right+1]中找到第一个大于val的位置l，这里使用二分进行查找
            l, r = left + 1, right
            while l <= r:
                mid = l + (r - l) // 2
                if arr[mid] > val:
                    r = mid - 1
                else:
                    l = mid + 1
            node.left = dfs(left + 1, l - 1)
            node.right = dfs(l, right)
            return node
        return dfs(0, len(arr) - 1)

class Codec1:
    # 思路1：通用方法：带None结点的前序遍历
    def serialize(self, root: Optional[TreeNode]) -> str:
        # 二叉树的栈前序遍历法
        """Encodes a tree to a single string.
        """
        node = root
        stack = []
        result = ""
        while node or stack:
            while node:
                result += f"{node.val},"
                stack.append(node)
                node = node.left
            result += "#,"  # 代表None结点的访问
            node = stack.pop()
            node = node.right
        result += "#,"  # 这是最后一个None节点
        return result

    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree.
        """
        # 第一步，解析出二叉树的前序序列
        arr = []
        nodeStr = ""
        for i in range(len(data)):
            if data[i] == ",":
                arr.append(nodeStr)
                nodeStr = ""
            else:
                nodeStr += data[i]
        # 第二步，深度优先搜索进行构建树；这里使用一个队列进行动态更新先序序列，达到O(n)的效果
        def dfs(arr:list[str]) -> TreeNode:
            nodeStr = arr.pop(0)
            if nodeStr == "#":
                return None
            else:
                node = TreeNode(int(nodeStr))
                node.left = dfs(arr)
                node.right = dfs(arr)
                return node
        return dfs(arr)
        
        

# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans

c++代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        TreeNode *node = root;
        stack<TreeNode*> s;
        string result = "";
        while (node != NULL || !s.empty()) {
            while (node != NULL) {
                result += to_string(node -> val) + ",";
                s.push(node);
                node = node -> left;
            }
            node = s.top();
            s.pop();
            node = node -> right;
        }
        return result;
    }

    TreeNode* dfs(int left, int right, vector<int>& arr) {
        if (right < left) {
            return NULL;
        }
        int val = arr[left];
        TreeNode *node = new TreeNode(val);
        int l = left + 1, r = right;
        int mid;
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (arr[mid] > val) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        node -> left = dfs(left + 1, l - 1, arr);
        node -> right = dfs(l, right, arr);
        return node;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<int> arr;
        string nodeStr = "";
        for (int i = 0; i < data.size(); i++) {
            if (data[i] == ',') {
                arr.push_back(stoi(nodeStr));
                nodeStr = "";
            } else {
                nodeStr += data[i];
            }
        }
        return dfs(0, arr.size() - 1, arr);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;

4.执行结果