449. Serialize and Deserialize BST

Description

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Constraints

The number of nodes in the tree is in the range [0, 104].
0 <= Node.val <= 104
The input tree is guaranteed to be a binary search tree.

Approach

Examples

Input: root = [2, 1, 3]

Output: [2, 1, 3]

Solutions

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

/**
 * Time complexity : 
 * Space complexity : 
 */

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        StringBuilder sb = new StringBuilder();
        
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node != null) {
                sb.append(node.val).append(",");
                stack.push(node.right);
                stack.push(node.left);
            } else {
                sb.append("#,");
            }
        }
        return sb.substring(0, sb.length()-1);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null) return null;
        
        return helper(data.split(","), new int[]{0});
    }
    
    private TreeNode helper(String[] values, int[] index) {
        if("#".equals(values[index[0]])) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(values[index[0]]));
        
        index[0] += 1;
        node.left = helper(values, index);
        
        index[0] += 1;
        node.right = helper(values, index);
        
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;

        StringBuilder sb = new StringBuilder();
        serialize(root, sb);

        return sb.substring(0, sb.length()-1);
    }
    
    private void serialize(TreeNode node, StringBuilder sb) {
        if(node == null) {
            sb.append("#,");
            return;
        }
        sb.append(node.val).append(",");
        serialize(node.left, sb);
        serialize(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null) return null;
        
        return helper(data.split(","), new int[]{0});
    }
    
    private TreeNode helper(String[] values, int[] index) {
        if("#".equals(values[index[0]])) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(values[index[0]]));
        
        index[0] += 1;
        node.left = helper(values, index);
        
        index[0] += 1;
        node.right = helper(values, index);
        
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;

Follow up

Previous423. Reconstruct Original Digits from English Next450. Delete Node in a BST

Last updated 5 years ago

hashtagDescription

hashtagConstraints

hashtagApproach

hashtagLinks

hashtagExamples

hashtagSolutions

hashtagFollow up