449. 序列化和反序列化二叉搜索树

题目

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

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

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

示例 1：

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

示例 2：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/serialize-and-deserialize-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这是「297. 二叉树的序列化与反序列化」的特殊情况。因为是二叉搜索树，所以中序遍历就是有序的，那么序列化时只需要进行先序遍历或者后序遍历，反序列化时，将数据排序就得到中序遍历结果，根据「先序和中序」或者「后序和中序」就可以还原一棵树。

代码

public class Codec {
    public String serialize(TreeNode root) {
        // 序列化时先序遍历，保存为字符串
        List<Integer> list = new ArrayList<Integer>();
        preOrder(root, list);
        String str = list.toString();
        return str.substring(1, str.length() - 1);
    }
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }
        // 将string还原为int数组，同时排序后可以获得中序遍历结果
        String[] arr = data.split(", ");
        int n = arr.length;
        int[] preorder = new int[n];
        int[] inorder = new int[n];
        for (int i = 0; i < n; i++) {
            preorder[i] = Integer.parseInt(arr[i]);
            inorder[i] = Integer.parseInt(arr[i]);
        }
        Arrays.sort(inorder);
        // 根据先序和中序结果还原二叉树，105题
        return buildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
    private void preOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }
    private TreeNode buildTree(int[] preorder, int[] inorder, int pre_l, int pre_r, int in_l, int in_r) {
        if (pre_l > pre_r || in_l > in_r) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[pre_l]);
        int k = in_l;
        while (inorder[k] != preorder[pre_l]) {
            k++;
        }
        root.left = buildTree(preorder, inorder, pre_l + 1, pre_l + k - in_l, in_l, k - 1);
        root.right = buildTree(preorder, inorder, pre_l + k - in_l + 1, pre_r, k + 1, in_r);
        return root;
    }
}