Accepted short Java O(N) recursive solution


  • 0
    D

    Serialization is done in pre-order as usual. Minimum space used to represent serialized BST. Deserialization logic recursively parses the pre-ordered string list, as is. Here I am using a TreeNode object reference (instead of global static variable) to keep track of array index over recursion calls.

    The only caveat I see is if there are more than Integer.MAX_VALUE number of nodes in a BST. In that case the int 32 counter would roll over.

    Any suggestions/comments are welcome.

    public class Codec {
        public String serialize(TreeNode root) {
            if(root == null)
                return "";
            return root.val + " " + serialize(root.left) + serialize(root.right);
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data.length()==0)
                return null;
            TreeNode index = new TreeNode(0);
            String[] str = data.split(" ");
            return helper(str, index, Integer.MAX_VALUE);
        }
    
        private TreeNode helper(String[] data, TreeNode index, int max) {
            TreeNode node = new TreeNode(Integer.parseInt(data[index.val]));
            index.val++;
            node.left = index.val < data.length && Integer.parseInt(data[index.val]) <= node.val?helper(data, index, node.val):null;
            node.right = index.val < data.length && Integer.parseInt(data[index.val]) > node.val && Integer.parseInt(data[index.val]) <= max?helper(data, index, max):null;
            return node;
        }
    }
    

Log in to reply
 

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