Most concise Java solution so far. Recursive. Preorder + BST property


  • 0
    L
    public class Codec {
        
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if(root == null) {return "";}
            String l = serialize(root.left), r = serialize(root.right);
            String res = "" + root.val + (l != "" ? "," + l : "") + (r != "" ? "," + r : "");
            return res; 
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data == "") {return null;}
            int[] vals = Stream.of(data.split(",")).mapToInt(Integer::valueOf).toArray();
            return deserHelper(vals, 0, vals.length);
        }
        private TreeNode deserHelper(int[] vals, int s, int e) {
            if(s >= e) {return null;}
            TreeNode root = new TreeNode(vals[s]);
            int rChildPos = e;
            for(int i = s + 1; i < e; i++) {
                if(vals[i] > root.val) {
                    rChildPos = i;
                    break;
                }
            }
            root.left = deserHelper(vals, s + 1, rChildPos);
            root.right = deserHelper(vals, rChildPos, e);
            return root;
        }
    }
    

    The difference of this question to #297 is that we can use BST property to make the serialized string more concise, i.e. not use special character to represent null node.

    The property of binary tree recovery: any two different traversal sequences can recover the original binary tree. E.g. preorder and inorder traversal sequence can recover the binary tree.

    Because BST implicitly tells us the inorder traversal, we will serialize it to preorder or postorder sequence. Here I use preorder sequence.

    When we deserialize a preorder sequence, we know the first element of the preorder sequence is the root of the current sequence. To find the left subtree and right subtree, we go through each node in the sequence until we find a value larger than the root, which is the start of the right subtree.


Log in to reply
 

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