Simple Java solution


  • 0
    L

    Since it is a BST, no special tricks are required rather than writing into a string in a preorder (or, postorder as well). Look at the string, find the root and the figure out the left and right subtrees by checking which part of the string is lesser than the root. Here is the code that does it:

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if(root==null) {
                return null;
            }
            StringBuilder builder = new StringBuilder();
            serializeHelper(root,builder);
            return builder.toString().trim();
        }
        private void serializeHelper(TreeNode root, StringBuilder builder) {
            if(root==null) {
                return;
            }
            builder.append(root.val);
            builder.append(' ');
            serializeHelper(root.left,builder);
            serializeHelper(root.right,builder);
        }
        
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data==null) {
                return null;
            }
            String[] arr = data.split(" ");
            List<String> list = Arrays.asList(arr);
            return deserializeHelper(list);
        }
        
        private TreeNode deserializeHelper(List<String> list) {
            if(list==null || list.isEmpty()) {
                return null;
            }
            TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
            //left subtree is till we find first non-smaller value.
            int i=1;
            while(i<list.size() && Integer.valueOf(list.get(i))<Integer.valueOf(list.get(0))) {
                i++;
            }
            root.left = deserializeHelper(list.subList(1,i));
            root.right = deserializeHelper(list.subList(i,list.size()));
            return root;        
            
        }
    

Log in to reply
 

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