LintCode - Binary Tree Serialization

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'.

There is no limit of how you deserialize or serialize a binary tree, you only need to make sure you can serialize a binary tree to a string and deserialize this string to the original structure.

Example

An example of testdata: Binary tree{3,9,20,#,#,15,7}, denote the following structure:

  3
 / \
9  20
  /  \
 15   7

Our data serialization use bfs traversal. This is just for when you got wrong answer and want to debug the input.

You can use other method to do serializaiton and deserialization.

Analysis:

At first, I want to use queue but the coding seem to be very difficult to understand and error prone. Using recursive is is a better decision in term of code elegency, dispite of the worse performance.

Serialization step is very straight but very important. If there is a misconsideration in the serialization, de-serialization will need to be rewrite. I made a mistake in writing it as

        if (root == null) {
            return "";
        }
        return root.val + "<" + serialize(root.left) + serialize(root.right) + ">";

it should have been.

        if (root == null) {
            return "";
        }
        return root.val + "<" + serialize(root.left) + ">" + "<" + serialize(root.right) + ">";

During the de-serialization,

1. one needs to pay attention to the matching brackets and whether the outermost brackets should be carried down for the next recursion. It should be excluded because in serialization, root.val is without a braket.
2. the number could be more than 1 digit. A simple data.charAt(x) to get the number is wrong.
3. there are two ways to convert a char to integer: char - '0' vs. Integer.valueOf(c).

Solution

    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        return root.val + "<" + serialize(root.left) + ">" + "<" + serialize(root.right) + ">";
    }

    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }

        TreeNode root = new TreeNode(-1);
        helper(root, true, data);
        return root.left;
    }

    public void helper(TreeNode root, Boolean left, String data) {
        if (data.length() <= 2) {
            return;
        }

        if (data.charAt(0) != '<' && data.charAt(0) != '>') {
            int value = Integer.valueOf(data.substring(0, data.indexOf('<')));
            if (left) {
                root.left = new TreeNode(value);
                root = root.left;
            } else {
                root.right = new TreeNode(value);
                root = root.right;
            }
        }

        int rightIndex = findRightChildIndex(data);
        if (rightIndex == -1) {
            return;
        }

        helper(root, true, data.substring(2, rightIndex));

        if (rightIndex + 1 < data.length()) {
            helper(root, false, data.substring(rightIndex + 1, data.length() - 1));
        }
    }

    public int findRightChildIndex(String data) {
        if (data.length() == 0) {
            return -1;
        }
        int count = 0;
        for (int i = 0; i < data.length(); i++) {
            if (data.charAt(i) == '<') {
                count++;
            }

            if (data.charAt(i) == '>') {
                count--;
                if (count == 0 && i + 1 < data.length()) {
                    return i + 1;
                }
            }
        }
        return -1;
    }