Java, O(n) serialize and O(nlogn) deserialize


  • 0
    D

    My idea is easy, encode BST using DFS, preorder, separate each value by one space.
    when deserialize the string, first get the root, and rebuild the BST by its rule.

    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) 
        {
            StringBuilder series = new StringBuilder();
            serializeHelper(root, series);
            return series.toString();
        }
        
        private void serializeHelper(TreeNode n, StringBuilder ser)
        {
            if (n == null) return;
            
            // encode with space to separate each node's value
            ser.append(n.val).append(' ');
            serializeHelper(n.left, ser);
            serializeHelper(n.right, ser);
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) 
        {
            if (data.equals("") || data == null) return null;
            String[] val = data.split(" ");
            
            TreeNode root = new TreeNode(Integer.parseInt(val[0]));
            for (int i = 1; i < val.length; i++)
            {
                rebuild(root, Integer.parseInt(val[i]));
            }
            return root;
        }
        
        private void rebuild(TreeNode root, int v)
        {
            TreeNode p = root;
            // rebuild the binary search tree
            while (true)
            {
                if (v > p.val )
                {
                    if (p.right == null) { p.right = new TreeNode(v); break; }
                    p = p.right;
                }
                else
                {
                    if (p.left == null ) { p.left = new TreeNode(v); break; }
                    p = p.left;
                }
            }
        }
    }
    

    In worst case, for example, chaining, rebuild will take O(n^2)


Log in to reply
 

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