449. Serialize and Deserialize BST

public class Codec {
    private static final String COMMA = ",";

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

    private void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            return;
        }

        sb.append(root.val).append(COMMA); // 只需要在每个值后面追加分隔符
        // 注意左右子节点需要递归调用该方法，不要调用错了
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }

        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(COMMA)));
        return deserialize(queue, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private TreeNode deserialize(Queue<String> queue, int minValue, int maxValue) {
        if (queue.isEmpty()) { // 注意此处不要漏掉判空
            return null;
        }

        int rootVal = Integer.parseInt(queue.peek()); // 注意此处判断大小前不要 poll
        if (rootVal < minValue || rootVal > maxValue) {
            return null;
        }

        queue.poll();
        TreeNode root = new TreeNode(rootVal);
        root.left = deserialize(queue, minValue, rootVal);
        root.right = deserialize(queue, rootVal, maxValue);
        return root;
    }
}

此题 rootVal < minValue || rootVal > maxValue 是关键，节省了对空节点序列化的空间。

Reference

449. Serialize and Deserialize BST
the General Solution for Serialize and Deserialize BST and Serialize and Deserialize BT - LeetCode