Java solution (beats 98%)


  • 0
    E

    Solution inspired by protocol buffers. It should be possible to optimize the string<->int conversion further as there is really no need to serialize it so a human readable value.

    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder out = new StringBuilder();
            serialize(root, out);
            return out.toString();
        }
        
        private void serialize(TreeNode node, StringBuilder out) {
            if (node == null) {
                out.append('0');
            }
            else {
                String valStr = Integer.toString(node.val);
                out.append((char)('0' + valStr.length())).append(valStr);
                serialize(node.left, out);
                serialize(node.right, out);
            }
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            return deserialize(data, new Pos());
        }
        
        private TreeNode deserialize(String data, Pos pos) {
            int valSize = (int)(data.charAt(pos.val) - '0');
            pos.val++;
            if (valSize == 0) return null;
            String valStr = data.substring(pos.val, pos.val + valSize);
            pos.val += valSize;
            TreeNode node = new TreeNode(Integer.parseInt(valStr));
            node.left = deserialize(data, pos);
            node.right = deserialize(data, pos);
            return node;
        }
        
        class Pos {
            int val;
        }
        
    }
    

  • 0
    X

    @erikandre Consider 2147483647, you will end up using a string "102147483647" which is 12 * 2 * 8 = 192 bits where original int is 32 bits. That's not what serialization should be.


  • 0
    E

    @xuechao Having a smaller output than the input is no requirement of this problem, and it is by no means a general requirement for a data serialization format.

    To quote from wikipedia: "serialization is the process of translating data structures or object state into a format that can be stored (for example, in a file or memory buffer, or transmitted across a network connection link) and reconstructed later in the same or another computer environment."

    Several data formats that are used for serialization (such as xml and json) are not particularly efficient but are instead used for other reasons, like ease of use and readability.


Log in to reply
 

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