449. Serialize and Deserialize BST 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class Codec {

    private static final String NULL = "null";
    private static final String COMMA = ",";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        // root, left, right
        if (root == null) {
            return NULL;
        }

        StringBuilder sb = new StringBuilder();
        dfs(sb, root);
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    private void dfs(StringBuilder sb, TreeNode root) {
        sb.append(root.val).append(COMMA);
        if (root.left != null) {
            dfs(sb, root.left);
        }
        if (root.right != null) {
            dfs(sb, root.right);
        }
    }

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

        String[] nodeStrings = data.split(COMMA);
        int[] nodeValues = new int[nodeStrings.length];
        for (int i = 0; i < nodeStrings.length; i++) {
            nodeValues[i] = Integer.parseInt(nodeStrings[i]);
        }
        return deserialize(nodeValues, 0, nodeValues.length - 1);
    }

    private TreeNode deserialize(int[] nodeValues, int startIndex, int endIndex) {
        if (startIndex > endIndex) {
            return null;
        }

        TreeNode root = new TreeNode(nodeValues[startIndex]);
        int rightStartIndex = startIndex + 1;
        while (rightStartIndex <= endIndex && nodeValues[rightStartIndex] < root.val) {
            rightStartIndex++;
        }

        root.left = deserialize(nodeValues, startIndex + 1, rightStartIndex - 1);
        root.right = deserialize(nodeValues, rightStartIndex, endIndex);
        return root;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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 是关键，节省了对空节点序列化的空间。

References

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