LeetCode #449 Serialize and Deserialize BST


  • 0
    C

    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.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.