LeetCode #449 Serialize and Deserialize BST

chinahechuan

Solution

We can use different forms to serialize the tree and the deserialize method depend on how we serialize it.

Part #1 Serialize

Since the left child and right child are different, so we have store both the children even if one of them is null. We can consider the form like this:

    { val { left.val {...} {...} } { right.val {...} {...} } }

Thus, we can traverse the tree in pre-order to construct the result. The length of result is 4n + Σlength(val) .

java

 // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return serial(root).toString();
    }
    private StringBuilder serial(TreeNode root){ // traverse the tree in pre-order
        if(root == null) return new StringBuilder("{}");
        return new StringBuilder("{")
                .append(root.val)    //val
                .append(serialize(root.left))  //left
                .append(serialize(root.right))  //right
                .append("}");
    }

Complexity Analysis

Time complexity : O(n). Traverse the tree in pre-order.

Part #2 Deserialize

In the same way, we can deserialize the string in pre-order

java

 // Decodes your encoded data to tree.
    int begin = 0;
    public TreeNode deserialize(String data) {
        return findChild(data);
    }
    private int findVal(String data){
        int index = begin;
        while(data.charAt(index)!='{'){index++;}
        int val = Integer.parseInt(data.substring(begin, index));
        begin = index;
        return val;
    }
    private TreeNode findChild(String data){
        if(data.charAt(begin+1) == '}') {
            begin += 2;
            return null;
        }
        begin++;
        TreeNode root = new TreeNode(findVal(data));
        root.left = findChild(data);
        root.right = findChild(data);
        begin++;
        return root;
    }

Complexity Analysis

Time complexity : O(n). We just traverse the string once.