题目链接

英文链接：https://leetcode.com/problems/serialize-and-deserialize-bst/

中文链接：https://leetcode-cn.com/problems/serialize-and-deserialize-bst/

题目详述

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

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

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

注意：不要使用类成员/全局/静态变量来存储状态。你的序列化和反序列化算法应该是无状态的。

题目详解

LeetCode297-二叉树的序列化与反序列化是二叉树的序列化的反序列化，而本题是二叉搜索树的序列化的反序列化。二叉搜索树也是二叉树，可以直接运用二叉树的序列化与反序列化操作。
由于题目要求编码的字符串应尽可能紧凑，结合二叉搜索树的性质，我们可以在序列化的时候省略表示 null 的字符，在反序列化的时候正确还原即可。

public class LeetCode_00449 {

    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            encode(root, sb);
            return sb.toString();
        }

        private void encode(TreeNode root, StringBuilder sb) {
            // 为 null 直接返回，不再添加额外字符表示 null
            if (root == null) {
                return;
            }
            sb.append(root.val).append('_');
            encode(root.left, sb);
            encode(root.right, sb);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            // 解析 ""
            if (data.isEmpty()) {
                return null;
            }
            String[] s = data.split("_");
            int[] index = new int[]{0};
            return decode(s, index, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }

        private TreeNode decode(String[] s, int[] index, int min, int max) {
            if (index[0] == s.length) {
                return null;
            }
            // 不匹配则返回
            int val = Integer.parseInt(s[index[0]]);
            if (val < min || val > max) {
                return null;
            }
            ++index[0];
            TreeNode root = new TreeNode(val);
            root.left = decode(s, index, min, val);
            root.right = decode(s, index, val, max);
            return root;
        }
    }
}