297. Serialize and Deserialize Binary Tree

, , ,

DFS

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
public class Codec {
    
    private static final String NULL = "null";
    private static final String COMMA = ",";

    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }

        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    private void serialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL).append(COMMA);
            return;
        }

        sb.append(node.val).append(COMMA);
        serialize(node.left, sb);
        serialize(node.right, sb);
    }

    private static class State {
        private int index;
    }

    public TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }

        String[] nodes = data.split(COMMA);

        State state = new State();
        return deserialize(nodes, state);
    }

    private TreeNode deserialize(String[] nodes, State state) {
        String nodeStr = nodes[state.index++];
        if (nodeStr.equals(NULL)) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(nodeStr));
        root.left = deserialize(nodes, state);
        root.right = deserialize(nodes, state);
        return root;
    }

}

LL Parser

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class Codec {

    private static final String NULL = "null";
    private static final char LEFT_BRACKET = '(';
    private static final char RIGHT_BRACKET = ')';

    public String serialize(TreeNode root) {
        // Grammar: T = (T) num (T) | null

        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

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

        sb.append(LEFT_BRACKET);
        serialize(root.left, sb);
        sb.append(RIGHT_BRACKET);
        sb.append(root.val);
        sb.append(LEFT_BRACKET);
        serialize(root.right, sb);
        sb.append(RIGHT_BRACKET);
    }

    private static class IndexHolder {
        private int index;
    }

    public TreeNode deserialize(String data) {
        IndexHolder indexHolder = new IndexHolder();

        return deserialize(data, indexHolder);
    }

    private TreeNode deserialize(String data, IndexHolder indexHolder) {
        if (data.charAt(indexHolder.index) == LEFT_BRACKET) {
            indexHolder.index++; // skip left bracket
            TreeNode root = new TreeNode(-1);
            root.left = deserialize(data, indexHolder);
            indexHolder.index++; // skip right bracket
            root.val = parseInt(data, indexHolder);
            indexHolder.index++; // skip left bracket
            root.right = deserialize(data, indexHolder);
            indexHolder.index++; // skip right bracket

            return root;
        } else {
            indexHolder.index += 4;
            return null;
        }
    }

    private int parseInt(String data, IndexHolder indexHolder) {
        int sign = 1;
        if (data.charAt(indexHolder.index) == '-') {
            sign = -1;
            indexHolder.index++;
        }

        int value = 0;
        while (Character.isDigit(data.charAt(indexHolder.index))) {
            value = value * 10 + data.charAt(indexHolder.index) - '0';
            indexHolder.index++;
        }

        return value * sign;
    }
}

BFS

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
60
61
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) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append(NULL);
            } else {
                sb.append(node.val);
                queue.offer(node.left);
                queue.offer(node.right);
            }
            sb.append(COMMA);
        }

        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.split(COMMA);
        String rootStr = strs[0];
        if (rootStr.equals(NULL)) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(rootStr));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int index = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                continue;
            }
            node.left = strToTreeNode(strs[index++]);
            node.right = strToTreeNode(strs[index++]);
            queue.offer(node.left);
            queue.offer(node.right);
        }

        return root;
    }

    private TreeNode strToTreeNode(String str) {
        if (str.equals(NULL)) {
            return null;
        } else {
            return new TreeNode(Integer.parseInt(str));
        }
    }

}

关键在于序列化空节点。

References

297. Serialize and Deserialize Binary Tree
剑指 Offer 37. 序列化二叉树
剑指 Offer II 048. 序列化与反序列化二叉树